First Unique Character in a String Python

This tutorial will show various approaches to finding the first unique character in a given string. For instance, the result should be "n" if the given string is "stringstutorial," and "S" if the given string is "StringsTutorial".

Explanation

Input: "stringstutorial"

Explanation:

Step 1: Creating a frequency list of the characters for the given string

freq['s'] = 2

freq['t'] = 3

freq['r'] = 2

freq['i'] = 2

freq['n'] = 1

freq['g'] = 1

freq['u'] = 1

freq['o'] = 1

freq['a'] = 1

freq['l'] = 1

Step 2: Find the first character having a unit frequency.

Creating a Frequency Hash Map

If a character only appears once in the given string, it is considered a non-repeating character. Calculating the frequency of each letter in the string sequence and determining which letter has a frequency of 1 are the steps in locating such unique characters. A hash map, which maps characters to their corresponding frequencies and allows us to concurrently modify the frequency of the characters we have already encountered in constant time, is an effective tool for this work. In the ASCII system, 256 unique characters are the limit. So, the maximum length of a hash map is 256. Reread the string, and the 1st letter whose frequency is equal to one is the solution.

Algorithm:

1. Create a hash map to associate each character with its frequency.
2. Use a pointer to navigate the input string.
3. Modify the number of characters now present in the hash map.
4. Next, go through the string once more to determine whether the present character has frequency = 1.
5. Resume the traverse if the frequency exceeds 1.
6. If not, end the loop and output the present character as the solution.

Code

Output

The first unique character is n 

Finding the Unique Character by Traversing the String Only Once

The primary method requires O(n) runtime, although we can make it faster in the application. The count array is constructed in the first step of the procedure by iteratively traversing the text in O(n) runtime. This step makes sense. However, the second portion, where we replay the string's initial non-repeater, isn't a good idea.

The string is anticipated much longer than our character set in actual circumstances. Consider DNA sequences, which may contain billions of letters and only have a four-letter alphabet. What transpires if the unique character is at the string's end? Then, it would require a lengthy scan.

Creating Hash Map and Traversing String Once

Instead of using the hash map, create a frequency array with the length of the character list as 256. By adding to the frequency array, we may store not only frequency but also the position of the letter's first appearance, such as (5, 36) for the letter, which indicates that it was recorded five times and originally appeared at position 36. To locate the first unique character, we only need to scan the frequency array rather than the string. Below is the implementation of this idea.

Code

Output

First unique character is n 

Creating a Frequency List and Looping Only Once

Creating a frequency list of a maximum of 256 characters. We can initialize all the items in this list to -1. We will iterate over the string's characters and examine if the list elements with this particular character have an index of 1 or not. If it turns out to be -1, we will change it to j; if it does not turn out to be -1, this indicates that the character has already been used; in that case, we will change it to -2.

All repeated characters will eventually be altered to -2, while all unique characters will still retain the index at which they first appeared. We can quickly discover the least or the initial index by iterating all the unique characters.

Code

Output

The first unique character is n 

Using in-built Functions of Python

Utilize the Counter() function to determine the frequency of all characters.

Go over the string and find which elements have frequency 1. Printing the unique character and breaking the loop there.

Code

Output

The first unique character is: n 

Using the find() Function of Strings

After the current letter, look up each subsequent letter. If it returns -1, it signifies that the letter only appears once, which is the present index.

Code

Output

The first unique character is: n 

Using the count() Function

If a character's count() within a string is 1, it indicates that the character is unique and not repeated. We will break the loop and print the first unique character we find.

Code

Output

The first unique character is n