Answer to Question #44994 in C for Palak

Question

A string is said to be "Beautiful", if it contains only non repetitive alphabets. Let S be the string with lower case alphabets, your task is to find out the longest "Beautiful sub-string" present in the given string S.

Input Format:

First line starts with T, which is the number of test cases. Each test case contains string S.

Output Format:

Print the first longest beautiful sub string present in the string S.

Constraints:
1<=T<=10

1<=|S|<=5500, S will contain only lower case alphabets.


Sample Input and Output

SNo. Input Output
1
2
ss
abcdeddd


s
abcde

Answer 1

//Answer on Question#44994 - Progamming - C
#include <stdio.h>
#include <string.h>
int main() {
   int T;
   char S[70];
   int len;
   int i, j;
   int curr;
   int start, finish;
   int pos['z' - 'a' + 1];
   scanf("%d", &T);
   while (T-- > 0) {
      scanf("%s", S);
      len = strlen(S);
      start = 0; 
      finish = 0;
      curr = 0;
      memset(pos, -1, sizeof(pos));
      for (i = 0; i < len; ++i) {
         if (pos[S[i] - 'a'] != -1) {
            if (i - curr > finish - start + 1) {
               start = curr;
               finish = i - 1;
            }
            for (j = curr; j < pos[S[i] - 'a']; ++j) {
               pos[S[j] - 'a'] = -1;
            } 
            curr = pos[S[i] - 'a'] + 1;
         } else {
            pos[S[i] - 'a'] = i;
         }
      }      
      if (len - curr > finish - start + 1) {
         start = curr;
         finish = len - 1;
      }
      for (i = start; i <= finish; ++i) {
         printf("%c", S[i]);
      }
      printf("\n");
   }
}