Kth Unique Character in a String

Problem

Given a string and a number k, find the k’th non-repeating character in the string. Consider a large input string with millions of characters and a small character set. How can you find the character by doing only one traversal of the input string?

Examples

Example 1

1
2
3

Input: str = "geeksforgeeks", k = 3
Output: r
Explanation: First non-repeating character is f, second is o, and third is r.

Example 2

1
2
3

Input: str = "geeksforgeeks", k = 2
Output: o
Explanation: Second non-repeating character is o.

Example 3

1
2
3

Input: str = "geeksforgeeks", k = 4
Output: Less than k non-repeating characters in input.
Explanation: There are only 3 non-repeating characters.

Solution

This problem is an extension of First non-repeating character.

Method 1 – Brute Force

Intuition

Check each character and see if it repeats. Count non-repeating characters until the k-th is found.

Approach

1. For each character in the string, check if it repeats by scanning the rest of the string.
2. If it does not repeat, increment a counter.
3. When the counter reaches k, return that character.

Complexity

• ⏰ Time complexity: O(n²) — For each character, we may scan the whole string.
• 🧺 Space complexity: O(1) — No extra space used.

Method 2 – Hash Map (O(n) time, two traversals)

Intuition

Count occurrences of each character, then find the k-th non-repeating character.

Approach

1. Traverse the string and count occurrences of each character using a hash map or array.
2. Traverse the string again, and for each character with count 1, increment a counter.
3. When the counter reaches k, return that character.

Complexity

• ⏰ Time complexity: O(n) — Two passes over the string.
• 🧺 Space complexity: O(1) — Fixed size for character set.

Method 3 – One Traversal with Index Array (O(n) time, O(1) space)

Intuition

Track both the count and the first index of each character. After one traversal, sort the indices to find the k-th non-repeating character.

Approach

1. Initialize two arrays of size 256 (for ASCII):

• count[x]: stores count of character x.
• index[x]: stores index of character x, or n if not present or repeating.

2. Traverse the string:

• For each character, increment its count.
• If count is 1, store its index.
• If count is 2, set its index to n.

3. Sort the index array. The k-th smallest valid index gives the k-th non-repeating character.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
  static const int MAX_CHAR = 256;
  char kthNonRepeating(const std::string& s, int k) {
    int n = s.size();
    int count[MAX_CHAR] = {0};
    int index[MAX_CHAR];
    for (int i = 0; i < MAX_CHAR; ++i) index[i] = n;
    for (int i = 0; i < n; ++i) {
      unsigned char x = s[i];
      count[x]++;
      if (count[x] == 1) index[x] = i;
      if (count[x] == 2) index[x] = n;
    }
    std::sort(index, index + MAX_CHAR);
    return (k > 0 && index[k-1] != n) ? s[index[k-1]] : '\0';
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
  static final int MAX_CHAR = 256;
  public char kthNonRepeating(String str, int k) {
    int n = str.length();
    int[] count = new int[MAX_CHAR];
    int[] index = new int[MAX_CHAR];
    Arrays.fill(index, n);
    for (int i = 0; i < n; i++) {
      char x = str.charAt(i);
      count[x]++;
      if (count[x] == 1) index[x] = i;
      if (count[x] == 2) index[x] = n;
    }
    Arrays.sort(index);
    return (k > 0 && index[k-1] != n) ? str.charAt(index[k-1]) : '\0';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
  def kth_non_repeating(self, s: str, k: int) -> str:
    MAX_CHAR = 256
    n = len(s)
    count = [0] * MAX_CHAR
    index = [n] * MAX_CHAR
    for i, ch in enumerate(s):
      x = ord(ch)
      count[x] += 1
      if count[x] == 1:
        index[x] = i
      if count[x] == 2:
        index[x] = n
    index.sort()
    return s[index[k-1]] if k > 0 and index[k-1] != n else ''

Complexity

• ⏰ Time complexity: O(n) — One traversal plus sorting a fixed-size array (O(1)).
• 🧺 Space complexity: O(1) — Arrays of constant size (256).