[PYTHON] Solution without using DP O(max(k^2,n))


#1

O(max(k^2,n)) where k is unique charachter present in string!
here condition If len(val2)>2 will be changed to if len(val2)>3 if we don’t want to allow ‘aaa’ as ‘aab’ is not allowed!

from collections import defaultdict
class Solution:
    # @param A : string
    # @return an integer
    def anytwo(self, A):
        ha = defaultdict(list)
        for i,val in enumerate(A):
            ha[val].append(i)
    
    for key,val in ha.items():
        if len(val)<2:
            continue
        
        for key2,val2 in ha.items():
            if len(val2)<2:
                continue
            if key == key2:
                if len(val2)>2:
                    return 1
                else:
                    continue
            if val[0]<val2[-2] and val[1]<val2[-1]:
                return 1
    return 0