Find the First Repeated Character in a String

Given a string, find the first character that repeats. If no character repeats, return None.

Input/Output Examples

plaintext
Example 1:
Input:
s = "programming"
Output: r
Explanation: The first character that repeats is r.

Example 2:
Input:
s = "swiss"
Output: s
Explanation: The first character that repeats is s.

Example 3:
Input:
s = "unique"
Output: None
Explanation: There are no repeated characters in the string.

Approach to Find the First Repeated Character in a String

  1. Use a Hash Set for Tracking Characters:
    • Initialize an empty hash set to keep track of characters as you iterate through the string.
  2. Check Each Character in Order:
    • For each character in the string, check if it exists in the set.
    • If the character is already in the set, it is the first repeated character; return it.
    • If the character is not in the set, add it to the set and continue.
  3. Return ‘None’ if No Repeated Character Found:
    • If the loop completes without finding a repeated character, return None.

C++ Program to Find the First Repeated Character in a String

cpp
#include <iostream>
#include <unordered_set>
using namespace std;

// Function to find the first repeated character
char firstRepeatedChar(const string& s) {
    unordered_set<char> seen;

    for (char c : s) {
        if (seen.find(c) != seen.end()) {
            return c;
        }
        seen.insert(c);
    }

    return '\0'; // Return null character if no repetition found
}

int main() {
    string s = "programming";
    char result = firstRepeatedChar(s);

    if (result == '\0') {
        cout << "No repeated character found." << endl;
    } else {
        cout << "First repeated character: " << result << endl;
    }

    return 0;
}

Java Program to Find the First Repeated Character in a String

java
import java.util.HashSet;

public class FirstRepeatedCharacter {

    // Function to find the first repeated character
    public static Character firstRepeatedChar(String s) {
        HashSet<Character> seen = new HashSet<>();

        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                return c;
            }
            seen.add(c);
        }

        return null; // Return null if no repetition found
    }

    public static void main(String[] args) {
        String s = "swiss";
        Character result = firstRepeatedChar(s);

        if (result == null) {
            System.out.println("No repeated character found.");
        } else {
            System.out.println("First repeated character: " + result);
        }
    }
}

Python Program to Find the First Repeated Character in a String

python
# Function to find the first repeated character
def first_repeated_char(s):
    seen = set()

    for c in s:
        if c in seen:
            return c
        seen.add(c)

    return None

# Example usage
if __name__ == "__main__":
    s = "unique"
    result = first_repeated_char(s)

    if result is None:
        print("No repeated character found.")
    else:
        print("First repeated character:", result)
  • Time Complexity: O(n), where n is the length of the string. Each character is processed once, making this an efficient linear-time solution.
  • Space Complexity: O(1) in practice, assuming the character set is limited (e.g., ASCII), since the maximum number of unique characters that can be stored in the set is constant.

DSA

8784

337

Related Articles