LeetCode Python Solutions: 387.First Unique Character in a String #python #coding #leetcode

ZeroStress LeetCode Python Solutions: 387.First Unique Character in a String#python #leetcode #programming #coding #tech #algorithm

Twitter: https://twitter.com/QiaoLiuCiao

problem description:
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0
Example 2:

Input: s = "loveleetcode"
Output: 2
Example 3:

Input: s = "aabb"
Output: -1

The solution intuition revolves around two key steps: counting the frequencies of characters and maintaining the order of unique characters.

To count the frequencies, we use a dictionary data structure called char_count. We iterate over the input string character by character, and for each character, we check if it already exists as a key in the dictionary. If it does, we increment its frequency by 1. If it doesn't, we add it as a new key with an initial frequency of 1.

This process allows us to efficiently count the frequencies of all the characters in the string. But how do we determine which character is the first non-repeating one?

Here comes the second step: maintaining the order of unique characters. We use a list called unique_chars to store the unique characters in the order they appeared in the original string. Whenever we encounter a new character, we add it to the list.

By the end of the first pass over the string, we have two important data structures: char_count, which holds the frequencies of characters, and unique_chars, which maintains the order of unique characters.

In the second pass, we iterate over the unique_chars list. For each character, we check its frequency in the char_count dictionary. If the frequency is equal to 1, it means the character is non-repeating. At this point, we have successfully found the first non-repeating character in the string.

To obtain the index of this non-repeating character, we utilize the index() method of the original string. By calling s.index(char), we retrieve the index of the character in the string and return it as the result.

If no non-repeating character is found during the second pass, we return -1 to indicate that there are no unique characters in the string.

In summary, the intuition behind this solution lies in efficiently counting character frequencies using a dictionary and maintaining the order of unique characters using a list. This approach allows us to identify the first non-repeating character and obtain its index.

Understanding the intuition behind the solution is crucial for building a solid foundation in problem-solving and algo’rithmic thinking. It equips us with the mindset and strategies to tackle similar challenges effectively.

The time complexity refers to the amount of time it takes for our solution to execute as the size of the input increases. In this case, the input is the given string.

We iterate over the string twice. First, we perform a pass to build the char_count ‘dictionary and populate the unique_chars list. This initial pass takes a linear time, meaning it grows proportionally to the size of the input string. Therefore, it has a time complexity of O(n), where n is the length of the string.

Then, in the second pass, we iterate over the unique_chars list, which contains unique characters in the order of their appearance. For each character, we check its frequency in the char_count dictionary. This step also takes linear time as we are examining each character exactly once. Hence, it has a time complexity of O(k), where k represents the number of unique characters in the string.

Since both passes are independent, we can consider their time complexities separately. Therefore, the overall time complexity of our solution is O(n + k).

We use two data structures: the char_count ‘dictionary and the unique_chars list.

The char_count ‘dictionary stores the frequencies of characters. In the worst case, if all characters in the string are unique, the ‘dictionary would contain k entries, where k is the number of unique characters. Hence, the space complexity for the ‘dictionary is O(k).

Similarly, the unique_chars list stores the unique characters in the order of their appearance. In the worst case, it can contain k elements as well. Therefore, the space complexity for the list is also O(k).

Since the space complexities of the ‘dictionary and list are both O(k), we can say that the overall space complexity of our solution is O(k).

Understanding the time and space complexities helps us assess the efficiency and scalability of our solution. It enables us to analyze how our code performs with larger inputs and make informed decisions when dealing with real-world scenarios.


00:00 Code
02:33 Main
10:00 End