Efficiently find first repeated character in a string without using any additional data structure in one traversal | Returns - 1 if all characters of str are unique . Assumptions : ( 1 ) str contains only characters from ' a ' to ' z ' ( 2 ) integers are stored using 32 bits ; An integer to store presence / absence of 26 characters using its 32 bits . ; If bit corresponding to current character is already set ; set bit in checker ; Driver code
def FirstRepeated ( string ) : NEW_LINE INDENT checker = 0 NEW_LINE pos = 0 NEW_LINE for i in string : NEW_LINE INDENT val = ord ( i ) - ord ( ' a ' ) ; NEW_LINE if ( ( checker & ( 1 << val ) ) > 0 ) : NEW_LINE INDENT return pos NEW_LINE DEDENT checker |= ( 1 << val ) NEW_LINE pos += 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT string = " abcfdeacf " NEW_LINE i = FirstRepeated ( string ) NEW_LINE if i != - 1 : NEW_LINE INDENT print " Char ▁ = ▁ " , string [ i ] , " ▁ and ▁ Index ▁ = ▁ " , i ; NEW_LINE DEDENT else : NEW_LINE INDENT print " No ▁ repeated ▁ Char " NEW_LINE DEDENT