Leetcode 2351: First Letter to Appear Twice
Given a string s of lowercase English letters, return the first letter that appears twice.
Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` consisting of lowercase English letters.
Example: Input: s = "axybczab"
Constraints:
• 2 <= s.length <= 100
• s consists of lowercase English letters.
• s contains at least one repeated letter.
Output: The output should be the first letter that appears twice in the string.
Example: Output: "a"
Constraints:
• The string will contain at least one repeated letter.
Goal: To find the first letter that appears twice in the string by tracking each letter's occurrence.
Steps:
• Iterate through the string and track the occurrence of each character.
• If a character appears again, return it immediately.
• If no character appears twice, the function should return the first character that repeats.
Goal: The solution must efficiently handle strings of length up to 100.
Steps:
• 2 <= s.length <= 100
• s consists of lowercase English letters.
• At least one letter repeats.
Assumptions:
• The input string will contain at least one repeated letter.
• Input: Input: s = "axybczab"
• Explanation: Here, the letter 'a' is the first to appear twice, so it is returned.
Approach: Use a set to track the characters that have been seen as we iterate through the string.
Observations:
• The problem is asking for the first repeating letter, so we should stop as soon as we encounter the second occurrence of a letter.
• A set can be used to keep track of characters we've already seen, and we return the first one that repeats.
Steps:
• Create an empty set to track the letters we've seen.
• Iterate over the string one character at a time.
• If the character is in the set, return it as the result.
• If the character is not in the set, add it to the set and continue.
Empty Inputs:
• The input will always contain at least one repeated letter, so there are no empty inputs.
Large Inputs:
• The solution should handle input strings up to the length of 100 efficiently.
Special Values:
• If the string contains multiple letters repeating, the first one encountered in the string is the answer.
Constraints:
• Ensure that the solution works for all strings of length between 2 and 100.
char repeatedCharacter(string s) {
vector<int> v(26);
for(char c:s){
v[c-'a']++;
if(v[c-'a']>1)return c;
}
return 'a';
}
1 : Function Declaration
char repeatedCharacter(string s) {
The function `repeatedCharacter` is declared, which accepts a string `s` and returns a character.
2 : Variable Initialization
vector<int> v(26);
A vector `v` of size 26 is initialized to count the occurrences of each lowercase letter ('a' to 'z').
3 : Loop Start
for(char c:s){
A loop is initiated to iterate over each character `c` in the string `s`.
4 : Count Character
v[c-'a']++;
For each character `c`, the corresponding index in the vector `v` is incremented to count the occurrences of that character.
5 : Condition Check
if(v[c-'a']>1)return c;
If the count of the current character exceeds 1, meaning it has been repeated, the function immediately returns that character.
6 : Return Statement
return 'a';
If no repeated character is found, the function returns 'a' by default, assuming no repeats are found in the string.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We only need to iterate through the string once, making the time complexity O(n), where n is the length of the string.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) because we use a set to track the letters we've seen, and the set's size can grow up to the size of the input string.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus