Saturday, July 21, 2012

Alternating Letters

An alternation in a string is defined to be two distinct characters (letters, digits, or punctuation) that alternate at least three times as the word is read from left to right. The word “boo” has no alternations, but “booboo” has “bobo” as an alternation of length 4. Upper and lower case characters are considered to be different, and so, “aragorn” contains the 4-element alternation “arar”, but “Aragorn” only has the 3-element alternation “rar”. Digits and punctuation may be used, so “a2b-c2d-” has the alternation “2-2-”. The objective of this problem is to write a program to find the length of the longest alternation in a word.
Examples:












































InputOutputExplanation
exasperatedLength = 5eaeae
counterintuitiveLength = 6tititi
insignificantLength = 6ininin
AragornLength = 3rar
a2b-c2d-Length = 42-2-
catLength = 0 No subsequence having length > 3
caLength = 0 No subsequence having length > 3


#include<stdio.h>
#include<string.h>
int main()
{
int A[256]={0},max=0,B[256]={0};
char s[1000];
scanf("%s",s);
for(int i=0;i<strlen(s);i++)
{
A[s[i]]++;
if(s[i]>max)
{
max=s[i];
}
}
int k=0;
for(int i=0;i<=max;i++)
{
if(A[i]!=0)
{
B[k]=i;
k++;
}
}
int maxcount=0;
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
int count=0;
int order=0;
char curr='';
for(int c=0;c<strlen(s);c++)
{
if(s[c]==B[i])
{
if(order==0)
{
count++;
order=1;
curr=B[i];
}
else if(curr==B[j])
{
count++;
curr=B[i];
}
}
else if(s[c]==B[j])
{
if(order==0)
{
count++;
order=1;
curr=B[j];
}
else if(curr==B[i])
{
count++;
curr=B[j];
}
}
}
if(maxcount<count)
{
maxcount=count;
}
}
}
if(maxcount>=3)
{
printf("%d\n",maxcount);
}
else
{
printf("0\n");
}
return 0;
}

No comments:

Post a Comment