Efficiently find first repeated character in a string without using any additional data structure in one traversal | Efficiently check First repeated character in C ++ program ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int FirstRepeated ( string str ) { int checker = 0 ; for ( int i = 0 ; i < str . length ( ) ; ++ i ) { int val = ( str [ i ] - ' a ' ) ; if ( ( checker & ( 1 << val ) ) > 0 ) return i ; checker |= ( 1 << val ) ; } return -1 ; } int main ( ) { string s = " abcfdeacf " ; int i = FirstRepeated ( s ) ; if ( i != -1 ) cout << " Char ▁ = ▁ " << s [ i ] << " ▁ and ▁ Index ▁ = ▁ " << i ; else cout << " No ▁ repeated ▁ Char " ; return 0 ; }