Strings, dynamic programming.

c-plus-plus
dynamic-programming
strings

#1

Given a string, find the length of the longest substring such that if a character is repeated in that substring, then it doesn’t add to the length. For example, the length of “abeap” in the string “aabeape” is 3, as “a” doesn’t count. Thus, for " aabeape", answer is 4, achieved by “beap”. For the string “qpaad”, it is 3, achieved by “qpaad”.


#2

use a hash… more than enough!


#3

@pushkarmishra : What is the time complexity that you want this to be solved in ? Obviously you could very simply do it in O(n^3) .
IN JAVA : If “str” is the given string :

 int maxCount = 0;
    for(int i = 0 ; i < str.length() ; i++) {
    for(int j = i ; j < str.length() ; j++) {
    int [] times = new int [26];
    for(int k = 0 ; k < 26 ; k++) {
        times[k] = 0 ;
    }
    for(int k = i ; k <= j ; k++) {
       times[Character.getNumericValue(str.charAt(k))-10]++;
    }
    int count = 0;
    for(int k = 0 ; k < 26 ; k++) {
        if(times[k] == 1 ) {
            count++;
        }
    }
    if(count>maxCount) {
       maxCount = count ;
    }
    }
    }
    System.out.println(maxCount) ;