Leetcode 387. First Unique Character in a String

Problem Explanation:

In this problem, we are given a string that contains only lowercase alphabets. We need to find the first non-repeating character in the string, and return its index. If no such character exists, we have to return -1.

Let's take one example to demonstrate the problem: Suppose the given string is "leetcode".

  • Firstly, we go through string for each character: 'l' -> l is the first character and until now we do not have any repeating characters. 'e' -> e is the next character, still no repeating character. 'e' -> Here, 'e' is repeating. So, the first non-repeating character is 'l'.

As we see 'l' is the first character, its index is zero. So, for "leetcode", the answer is 0.

Problem Approach and Solution Explanation:

Now, let's discuss how we can approach this problem.

One way to solve this problem is to use an array(say count[]) to store the frequencies of the characters in the string. As we are assuming that the string contains only lowercase alphabets, size 26 [from (a-z)] would be enough but to keep it more generic, we are taking the array of size 128.

  • Firstly, we loop through the string and update the count of each character in the count[] array.
  • After that, we again loop through the string and for each character, we check whether its count is 1. If it is, we return the index as it is the first non-repeating character otherwise, we proceed to the next character.
  • If we are not able to find any non-repeating character, we return -1 to denote that no such character exists.

The solution is very straightforward and it follows similar steps as discussed in the solution approach. It uses a character array to store the frequencies of characters in the string and then for each character, checks whether its count is 1.

Python Solution:

3class Solution:
4    def firstUniqChar(self, s: str) -> int:
5        # Create a frequency table
6        count = [0]*128
8        # Populate frequency table
9        for c in s:
10            count[ord(c)] += 1
12        # Look for first non-repeating character
13        for i in range(len(s)):
14            if count[ord(s[i])] == 1:
15                return i
17        return -1

Java Solution:

3public class Solution {
4    public int firstUniqChar(String s) {
5        int[] count = new int[128];
7        for (char c : s.toCharArray())
8            ++count[c];
10        for (int i = 0; i < s.length(); ++i)
11            if (count[s.charAt(i)] == 1)
12                return i;
14        return -1;
15    }

JavaScript Solution:

3var firstUniqChar = function(s) {
4    let count = new Array(128).fill(0);
6    for(let c of s)
7        ++count[c.charCodeAt(0)];
9    for(let i = 0; i<s.length; ++i)
10        if(count[s.charCodeAt(i)] == 1)
11            return i;
13    return -1;

C++ Solution:

3class Solution {
5    int firstUniqChar(string s) {
6        vector<int> count(128);
8        for (char c : s)
9            ++count[c];
11        for (int i = 0; i < s.length(); ++i)
12            if (count[s[i]] == 1)
13                return i;
15        return -1;
16    }

C# Solution:

3public class Solution {
4    public int FirstUniqChar(string s) {
5        int[] count = new int[128];
7        foreach (char c in s)
8            ++count[c];
10        for (int i = 0; i < s.Length; ++i)
11            if (count[s[i]] == 1)
12                return i;
14        return -1;
15    }

In conclusion, this problem of finding the first non-repeating character in a string showcases the usage of arrays for storing frequency counts of characters in the string. This is utilized in the approach of each solution for Python, JavaScript, Java, C++, and C#, where each uses a similar algorithm to solve the problem.

Inside a loop, each character frequency is calculated and stored in a count array. In the subsequent loop, the count of the current character is checked against 1. If it matches, the index is instantly returned as it indicates that this character is not being repeated in that string. If no such character is found by the end of the loop, -1 is returned to indicate that no non-repeating character was found in the string.

This problem helps to practice dealing with strings and arrays, and can be helpful in honing string manipulation skills and understanding the concept of frequency counts in arrays. The solution is effectively implemented in a variety of programming languages, including Python, JavaScript, Java, C++, and C#. These solutions are efficient, easy to understand and clearly highlight the adaptability of basic programming concepts across different coding languages.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫