algoadvance

Leetcode 2351. First Letter to Appear Twice

Problem Statement

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Clarifying Questions

  1. Input Constraints:
    • Can the string be empty?
    • Are there always at least two occurrences of one character?

    Assumption: The string is always non-empty and there is always at least one character that appears twice.

  2. Output Specifications:
    • Should the output be in the form of a character that appears twice in the string?

    Understood: Yes, return the first character that appears twice.

Strategy

  1. Using a Set to Track Seen Characters:
    • Iterate over the characters of the string.
    • Maintain a set to keep track of characters that have been seen.
    • If a character is already in the set, it is the first character to appear twice.
    • Return the first character that meets the criterion.
  2. Time Complexity:
    • The loop runs through the string once, and each insertion/check operation in the hash set is O(1).
    • Thus, the overall time complexity is O(n), where n is the length of the string.

Code

public class Solution {
    public char repeatedCharacter(String s) {
        Set<Character> seen = new HashSet<>();
        
        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                return c;  // Return the first character that appears twice
            }
            seen.add(c);
        }
        
        // As per problem constraints, we should never reach here.
        throw new IllegalArgumentException("No character appears twice in the given string");
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Example Test Cases
        System.out.println(solution.repeatedCharacter("abccbaacz"));  // Outputs 'c'
        System.out.println(solution.repeatedCharacter("abcddcba"));   // Outputs 'd'
    }
}

Explanation

  1. We initialize an empty hash set to keep track of characters we have seen so far.
  2. We iterate through each character in the string:
    • If the character is already in the set, it means we have encountered the character before, so we return it as the result.
    • Otherwise, we add the character to the set and continue checking the next characters.
  3. The set ensures constant-time complexity operations for insertion and lookup.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI