Problem: Longest K unique characters substring

*Difficulty: easy

Given a string you need to print the size of the longest possible substring that has exactly k unique characters. If there is no possible substring print -1.
Example
For the string aabacbebebe and k = 3 the substring will be cbebebe with length 7.
Input:
The first line of input contains an integer T denoting the no of test cases then T test cases follow. Each test case contains two lines . The first line of each test case contains a string s and the next line conatains an integer k.

Output:
For each test case in a new line print the required output.

Constraints:
1<=T<=100
1<=k<=10

Example:
Input:

2
aabacbebebe
3
aaaa
1
Output:
7
4

Implementation: Python 2.7

#code
def all_sub_string(k, string, all_substr):
    if k > len(string):
        return 
    elif k == len(string):
        all_substr.append(string)
        return
    else:
        for i in range(len(string)):
            if i + k > len(string):
                break
            all_substr.append(string[i:i+k])
        all_sub_string(k+1, string, all_substr)

def longest_k_unique_char_substr(all_substr, k):
    if k > len(all_substr[-1]):
        return -1
    max_length = -1
    for substr in all_substr:
        if len(substr) >= k and len(set(substr)) == k:
            if len(substr) > max_length:
                max_length = len(substr)
    return max_length
            

def main():
    t = input()
    for _ in xrange(t):
        string = raw_input().strip()
        k = input()
        all_substr = []
        all_sub_string(1, string, all_substr)
        print longest_k_unique_char_substr(all_substr, k)

if __name__ == '__main__':
    main()
Advertisements