When working with strings in Kotlin, you may encounter scenarios where you need to find the first character that does not repeat. This problem is common in text processing, competitive programming, and software development.

In this blog, we’ll walk through an efficient approach to finding the first non-repeating character in a string using Kotlin. We’ll also explore a detailed explanation of the logic, why it works, and how it can be optimized for better performance.

Understanding the Problem

Given a string, our goal is to identify the first character that appears only once. If all characters are repeated, we should return null or a suitable indicator that no unique characters exist.

Input: "abcdhbac"
Output: 'd'

Here, ‘a’, ‘b’, and ‘c’ are repeated, but ‘d’ appears only once, making it the first non-repeating character.

Step-by-Step Approach (HashMap-based )

To solve this problem efficiently, we follow these steps:

1. Use a HashMap (Mutable Map in Kotlin) to count occurrences of each character.
2. Loop through the string to populate the frequency map.
3. Loop through the string again to find the first character with a count of 1.
4. Return the first unique character found; otherwise, return null.

Kotlin Implementation

Now, let’s implement this approach in Kotlin:

fun findNonRepeatedLetter(str: String): Char? {
    val charCount = mutableMapOf<Char, Int>()

    // Count occurrences of each character
    for (char in str) {
        charCount[char] = charCount.getOrDefault(char, 0) + 1
    }
    // Find the first character with a count of 1
    for (char in str) {
        if (charCount[char] == 1) {
            return char
        }
    }
    
    return null // Return null if no unique character exists
}

fun main() {
    val str = "abcdhbac"
    val result = findNonRepeatedLetter(str)
    
    println("First non-repeating character: ${result ?: "None"}")
}

Here,

• Step 1: We create a mutable map charCount to store character frequencies.
• Step 2: We iterate over the string, updating the map with each character’s occurrence count.
• Step 3: We loop through the string again to check which character appears only once.
• Step 4: If found, we return it; otherwise, we return null.

Output

First non-repeating character: d

Why This Approach Works Efficiently

This method ensures an optimal time complexity of O(n):

• First loop (O(n)) — Counts character occurrences.
• Second loop (O(n)) — Finds the first unique character.
• Overall Complexity: O(n) + O(n) = O(n), making it very efficient.

Edge Cases to Consider

1. All Characters Repeated: Input: "aabbcc" Output: None
2. String with Only One Character: Input: "x" Output: x
3. Empty String: Input: "" Output: None
4. String with Multiple Unique Characters: Input: "kotlin" Output: k

Alternative Optimized Approach (Array-based)

Instead of using a HashMap, we can use an Array of size 256 (for ASCII characters) to store occurrences, making it even more memory-efficient for large-scale data.

fun findNonRepeatedLetterOptimized(str: String): Char? {
    val charArray = IntArray(256) // For ASCII characters
    
    for (char in str) {
        charArray[char.toInt()]++
    }
    
    for (char in str) {
        if (charArray[char.toInt()] == 1) {
            return char
        }
    }
    
    return null
}

Let’s walk through code and try to dry run it.

Step 1: Initialize charArray

The charArray will look like this initially (all zeros):

[0, 0, 0, 0, ..., 0]  // 256 zeros

Step 2: Count the characters

For each character in "abcdhbac", the array will be updated based on their ASCII values:

• ‘a’ has an ASCII value of 97, so charArray[97]++ (now charArray[97] = 1).
• ‘b’ has an ASCII value of 98, so charArray[98]++ (now charArray[98] = 1).
• ‘c’ has an ASCII value of 99, so charArray[99]++ (now charArray[99] = 1).
• ‘d’ has an ASCII value of 100, so charArray[100]++ (now charArray[100] = 1).
• ‘h’ has an ASCII value of 104, so charArray[104]++ (now charArray[104] = 1).
• ‘b’ has an ASCII value of 98 again, so charArray[98]++ (now charArray[98] = 2).
• ‘a’ has an ASCII value of 97 again, so charArray[97]++ (now charArray[97] = 2).
• ‘c’ has an ASCII value of 99 again, so charArray[99]++ (now charArray[99] = 2).

Now, the charArray looks like this (only showing relevant indexes):

charArray[97] = 2  // 'a' appears 2 times
charArray[98] = 2  // 'b' appears 2 times
charArray[99] = 2  // 'c' appears 2 times
charArray[100] = 1 // 'd' appears 1 time
charArray[104] = 1 // 'h' appears 1 time

Step 3: Find the first non-repeating character

• Now, we iterate through the string again:
• ‘a’: charArray[97] == 2 → Skip.
• ‘b’: charArray[98] == 2 → Skip.
• ‘c’: charArray[99] == 2 → Skip.
• ‘d’: charArray[100] == 1 → Return ‘d’ (First non-repeating character).

Thus, the output will be 'd'.

Execution Flow:

1. First loop: Count character occurrences in the string.
2. Second loop: Check for the first character that appears only once.
3. Return: Return the first non-repeating character or null if there are no non-repeating characters.

This approach is very efficient, with a time complexity of O(n), where n is the length of the string.

Why this approach is optimized?

• Space is constant: The array size is fixed (256), regardless of the length of the input string. This means the space complexity of the solution is O(1) (constant space), as the array size does not grow with the input size, and you can use it regardless of whether the string is long or short.
• No need for dynamic data structures like HashMap: The use of a fixed-size array eliminates the need for dynamically resizing a hash map as new characters are added, which would typically require reallocation of memory.

Conclusion

Finding the first non-repeating character in a string is a common problem, and Kotlin provides powerful tools like mutableMapOf and IntArray to solve it efficiently. The HashMap-based approach is easy to understand and works well in most cases, while the Array-based approach can be optimized for performance in certain situations.