{"id":1875,"date":"2024-03-06T22:00:00","date_gmt":"2024-03-06T22:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1875"},"modified":"2024-03-08T09:11:28","modified_gmt":"2024-03-08T09:11:28","slug":"first-unique-character-string","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/first-unique-character-string\/","title":{"rendered":"First Unique Character in a String (C++, Java, Python)"},"content":{"rendered":"\n

Data Structures is one of the most important subjects to conquer to become a good programmer. In this article, we will discuss the \u201cFirst Unique Character in a String\u201d problem from leetcode and how to code the solution.<\/p>\n\n\n\n

First Unique Character in a String problem<\/strong><\/h2>\n\n\n\n

In the First Unique Character in a String problem, we have given a string and we must find the index of the first non-repeating character from the string. <\/strong><\/p>\n\n\n\n

For example, if you have given a string \u201cfavtutor\u201d <\/strong>then non-repeating characters in this string are f, a, v, u, o, r. The first non-repeating character is ‘f’. So the index is 0. <\/p>\n\n\n\n

Let’s look at some more examples:<\/p>\n\n\n\n

Input<\/strong>: s = \u201camma\u201d<\/p>\n\n\n\n

Output:<\/strong> -1     (as all the characters in this string have more than one occurrence)<\/p>\n\n\n\n

Input:<\/strong> s = \u201cfavtutor\u201d<\/p>\n\n\n\n

Output<\/strong>: 0<\/p>\n\n\n\n

Input<\/strong>: s = \u201cabcac\u201d<\/p>\n\n\n\n

Output:<\/strong> 1<\/p>\n\n\n\n

\"Example<\/figure>\n\n\n\n

Note:  String only contains lowercase alphabetical characters.<\/p>\n\n\n\n

The easiest way is to go to each index and check if the same character is present in the string or not. <\/strong>If not, return this index; otherwise, check for the next index. If no such element is present, return -1.<\/p>\n\n\n\n

Let’s examine this approach on the string s = \u201cfavtutor.\u201d Simply, Iterate over the string and check if that character is present in that string or not. In this case, f is only present at index 0. So the answer is 0.<\/p>\n\n\n\n

Time Complexity here will be O(n^2), where \u2018n\u2019 is the size of the string. As we are iterating over two loops. One to go at each place, another to check if that character is present more than once or not. Space complexity will be O(1) as we are not using any extra space.<\/p>\n\n\n\n

Hash-Map Approach<\/strong><\/h2>\n\n\n\n

The brute force approach is taking too much time. We can reduce the time complexity if we use a hash map<\/a> to store the characters of the string. This will reduce the time complexity from O(n^2) to O( n log(n) ). <\/p>\n\n\n\n

Let\u2019s find out the steps involved:<\/p>\n\n\n\n

    \n
  1. Create a hash map that will store the frequency of each character.<\/li>\n\n\n\n
  2. Store each character on the map.<\/li>\n\n\n\n
  3. Iterate over the string and check the frequency of that character. If the frequency is one then return this index. Otherwise, check for the next index.<\/li>\n\n\n\n
  4. If there is no such character, return -1.<\/li>\n<\/ol>\n\n\n\n

    Time Complexity will be O( n log(n) ). Here n is the size of the string. As we are storing each character in the map and storing values in the map it requires log(n) time. Space complexity will be O(26), which is approximately O(1), as there are only 26 different characters. <\/p>\n\n\n\n

    Optimized Approach<\/strong><\/h2>\n\n\n\n

    In the hash map approach, we saw that if we store the frequency of each character we can easily find out the first non-repeating character. However, storing elements into the hash map requires Log(n) time complexity. This can be reduced if we use an array of size 26 and store the frequency using it. <\/p>\n\n\n\n

    Let’s examine this approach.<\/p>\n\n\n\n