#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct ll {
	char c;
	int active;
	struct ll *next;
	struct ll *orig_next;
	struct ll *prev;
	struct ll *orig_prev;
} _ll;
typedef struct ll LL;

LL *head=NULL;

int oppcase( char a, char b )
{
	if( tolower(a) == tolower(b) && a != b ) {
		return( 1 );
	}
	return( 0 );
}

int main(void)
{
	char base,minbase;
	char input[65536];
	FILE *f;
	int ct;
	int minpol=-1;
	LL *prev=NULL;

	f=fopen( "inp.final", "r" );
	if( !f ) {
		printf( "Failed to open inp.final.\n" );
		return(0);
	}
	fgets( input, 65535, f );
	ct=0;
	while( input[ct] ) {
		if( isalpha( input[ct] ) ) {
			LL *new;
			new=malloc(sizeof(LL));
			new->c=input[ct];
			new->active=1;
			new->next=NULL;
			new->prev=prev;
			new->orig_prev=prev;
			if( prev == NULL ) {
				head=new;
			} else {
				prev->next=new;
				prev->orig_next=new;
			}
			prev=new;
		}
		ct++;
	}

	base='a';
	while( base <= 'z' ) {
		int active;
		LL *curr=head;
		do {
			active=0;
			while( curr ) {
				if( tolower(curr->c) == base ) {
					curr->active=0;
					if( curr->next ) {
						curr->next->prev = curr->prev;
					}
					if( curr->prev ) {
						curr->prev->next = curr->next;
					}
					if( curr->prev ) {
						/* go back one just in case the previous now matches the next */
						curr=curr->prev;
					} else {
						curr=curr->next;
					}
					active++;
				} else {
					if( curr->next && oppcase( curr->c, curr->next->c ) ) {
						curr->active=0;
						curr->next->active=0;
						active++;
						if( curr->prev ) {
							curr->prev->next = curr->next->next;
							if( curr->next->next ) {
								curr->next->next->prev=curr->prev;
							}
							curr=curr->prev;
						} else {
							/* printf( "curr->prev is NULL\n" ); */
							curr=curr->next->next;
							curr->prev=NULL;
						}
					} else {
						curr=curr->next;
					}
				}
			}
		} while( active > 0 );

		/* count active */
		curr=head;
		active=0;
		while( curr ) {
			if( curr->active ) {
				active++;
			}
			curr=curr->next;
		}
		printf( "without %c active=%d\n", base, active );
		if( minpol == -1 || active < minpol ) {
			minpol=active;
			minbase=base;
		}
		/* fix pointers */
		curr=head;
		while( curr ) {
			curr->next=curr->orig_next;
			curr->prev=curr->orig_prev;
			curr->active=1;
			curr=curr->next;
		}
		base++;
	}
	printf( "minimum polymers = %d with base=%c\n", minpol, minbase );
}