Efficiently find first repeated character in a string without using any additional data structure in one traversal
Implement a space efficient algorithm to check First repeated character in a string without using any additional data structure in one traversal. Use additional data structures like count array, hash, etc is not allowed.
Examples :
Input : abcfdeacf Output : char = a, index= 6
The idea is to use an integer variable and uses bits in its binary representation to store whether a character is present or not. Typically an integer has at-least 32 bits and we need to store presence/absence of only 26 characters.
Implementation:
C++
// Efficiently check First repeated character // in C++ program #include<bits/stdc++.h> using namespace std; // 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 int FirstRepeated(string str) { // An integer to store presence/absence // of 26 characters using its 32 bits. int checker = 0; for ( int i = 0; i < str.length(); ++i) { int val = (str[i]- 'a' ); // If bit corresponding to current // character is already set if ((checker & (1 << val)) > 0) return i; // set bit in checker checker |= (1 << val); } return -1; } // Driver code 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; } |
Java
// Efficiently check First repeated character // in Java program public class First_Repeated_char { static int FirstRepeated(String str) { // An integer to store presence/absence // of 26 characters using its 32 bits. int checker = 0 ; for ( int i = 0 ; i < str.length(); ++i) { int val = (str.charAt(i)- 'a' ); // If bit corresponding to current // character is already set if ((checker & ( 1 << val)) > 0 ) return i; // set bit in checker checker |= ( 1 << val); } return - 1 ; } // Driver code public static void main(String args[]) { String s = "abcfdeacf" ; int i=FirstRepeated(s); if (i!=- 1 ) System.out.println( "Char = " + s.charAt(i) + " and Index = " +i); else System.out.println( "No repeated Char" ); } } // This code is contributed by Sumit Ghosh |
Python3
# Efficiently check First repeated character # in Python # 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 def FirstRepeated(string): # An integer to store presence/absence # of 26 characters using its 32 bits. checker = 0 pos = 0 for i in string: val = ord (i) - ord ( 'a' ); # If bit corresponding to current # character is already set if ((checker & ( 1 << val)) > 0 ): return pos # set bit in checker checker | = ( 1 << val) pos + = 1 return - 1 # Driver code string = "abcfdeacf" i = FirstRepeated(string) if i ! = - 1 : print ( "Char = " , string[i], " and Index = " , i) else : print ( "No repeated Char" ) # This code is contributed by Sachin Bisht |
C#
// C# program to Efficiently // check First repeated character using System; public class First_Repeated_char { static int FirstRepeated( string str) { // An integer to store presence/absence // of 26 characters using its 32 bits. int checker = 0; for ( int i = 0; i < str.Length; ++i) { int val = (str[i]- 'a' ); // If bit corresponding to current // character is already set if ((checker & (1 << val)) > 0) return i; // set bit in checker checker |= (1 << val); } return -1; } // Driver code public static void Main() { string s = "abcfdeacf" ; int i=FirstRepeated(s); if (i!=-1) Console.WriteLine( "Char = " + s[i] + " and Index = " + i); else Console.WriteLine( "No repeated Char" ); } } // This code is contributed by vt_m. |
PHP
<?php // Efficiently check First repeated character // in PHP 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 function FirstRepeated( $str ) { // An integer to store presence/absence // of 26 characters using its 32 bits. $checker = 0; for ( $i = 0; $i < strlen ( $str ); ++ $i ) { $val = (ord( $str [ $i ]) - ord( 'a' )); // If bit corresponding to current // character is already set if (( $checker & (1 << $val )) > 0) return $i ; // set bit in checker $checker |= (1 << $val ); } return -1; } // Driver code $s = "abcfdeacf" ; $i =FirstRepeated( $s ); if ( $i !=-1) echo "Char = " . $s [ $i ] . " and Index = " . $i ; else echo "No repeated Char" ; // This code is contributed by ita_c ?> |
Javascript
<script> // Efficiently check First repeated character // in Javascript program function FirstRepeated(str) { // An integer to store presence/absence // of 26 characters using its 32 bits. let checker = 0; for (let i = 0; i < str.length; ++i) { let val = (str[i]- 'a' ); // If bit corresponding to current // character is already set if ((checker & (1 << val)) > 0) return i; // set bit in checker checker |= (1 << val); } return -1; } // Driver code let s = "abcfdeacf" ; let i=FirstRepeated(s); if (i!=-1) document.write( "Char = " + s[i] + " and Index = " +i); else document.write( "No repeated Char" ); // This code is contributed by rag2127 </script> |
Output
Char = a and Index = 6
Time Complexity: O(n)
Auxiliary Space: O(1)
This article is contributed by Mr. Somesh Awasthi.
Contact Us