Question #44994

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

Expert's answer

`//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");

}

}

## Comments

## Leave a comment