Efficiently find first repeated character in a string without using any additional data structure in one traversal

Last Updated : 15 Jul, 2022

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>