Leetcode 387: First Unique Character in a String

Input: The input consists of a string s.

Example: s = "programming"

Constraints:

• 1 <= s.length <= 10^5

• s consists of only lowercase English letters

Output: Return the index of the first non-repeating character, or -1 if no such character exists.

Example: Output: 0

Constraints:

• The index should be within the range of the string length.

Goal: The goal is to find the first non-repeating character efficiently.

Steps:

• Create a frequency map of characters in the string.

• Traverse the string and check the frequency of each character.

• Return the index of the first character with a frequency of 1.

Goal: The algorithm should run efficiently for large inputs.

Steps:

• The time complexity should be linear, O(n).

• Space complexity should be O(n) for the frequency map.

Assumptions:

• The input string is valid and contains only lowercase English letters.

• Input: Input: "programming"

• Explanation: The character 'p' at index 0 is the first non-repeating character in the string.

Approach: The approach is to use a frequency map to count the occurrences of each character in the string, then traverse the string again to find the first character with a frequency of 1.

Observations:

• A frequency map will help us track the count of each character efficiently.

• By iterating through the string twice, once to build the frequency map and once to find the first non-repeating character, we can solve the problem in O(n) time.

Steps:

• Initialize a frequency map to store the count of each character in the string.

• Traverse the string to populate the frequency map.

• Iterate through the string again, checking the frequency map for the first character with a count of 1.

• Return the index of that character, or -1 if no such character exists.

Empty Inputs:

• The input string will always have at least one character.

Large Inputs:

• Ensure that the solution runs efficiently for strings with lengths up to 100,000.

Special Values:

• For strings where all characters repeat, return -1.

Constraints:

• Ensure that the algorithm handles edge cases efficiently.

int firstUniqChar(string s) {
    
    map<char, int> mp;
    for(char x: s) mp[x]++;
    
    for(int i = 0; i < s.size(); i++)
        if(mp[s[i]] == 1) return i;
    
    return -1;
}

1 : Function Definition

int firstUniqChar(string s) {

Define the function 'firstUniqChar' that takes a string 's' as input and returns the index of the first non-repeating character.

2 : Data Structure

    map<char, int> mp;

Declare a map 'mp' to store the frequency of each character in the string.

3 : Loop Iteration

    for(char x: s) mp[x]++;

Iterate through each character in the string 's' and increment its corresponding count in the map.

4 : Loop Iteration

    for(int i = 0; i < s.size(); i++)

Iterate through the string 's' by index.

5 : Condition Check

        if(mp[s[i]] == 1) return i;

Check if the character at index 'i' in the string has a count of 1 in the map (i.e., it's non-repeating). If true, return the index 'i'.

6 : Return Statement

    return -1;

Return -1 if no non-repeating character is found in the string.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we iterate over the string twice.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the frequency map used to store character counts.

Leetcode 387: First Unique Character in a String

Solution to LeetCode 387: First Unique Character in a String Problem

Explore →