75 Most Popular Coding Interview Questions (Blind 75)

Use the filter to quickly find patterns like Two Pointers, Sliding Window, Binary Search, Graphs (BFS/DFS), DP, and Trees/Tries.

Showing 1 of 1

Given a string, find the first non-repeating character in it.
Here is a Java solution:
```
class Solution { 
	public char firstUniqChar(String s) {
	int[] freq = new int[26];
	for (int i = 0; i < s.length(); i++) {
		freq[s.charAt(i) - 'a']++;
	}
	for (int i = 0; i < s.length(); i++) {
		if (freq[s.charAt(i) - 'a'] == 1) {
			return s.charAt(i);
		}
	}
	return ' ';
	}
}
```
Explanation:
The solution uses two arrays, `freq` and `index`, to store the frequency and position of each character in the string. It first iterates through the string and increments the frequency of each character in the `freq` array. Then, it iterates through the string again and returns the first character whose frequency is 1 in the `freq` array. If there is no such character, the function returns a space character. Time Complexity: O(n), where `n` is the length of the string. The algorithm performs two full traversals of the string, taking linear time. Space Complexity: O(1), the space used by the frequency array. Since the frequency array uses a fixed size of 26, the space complexity is constant.