Introduction

Finding the first non-repeated character in a string is a common problem in computer science. It can be particularly crucial in areas such as text processing, data analysis, or programming competitions. The optimal solution to this problem should exhibit a linear time complexity, $O(n)$, where $n$ is the length of the string. One effective approach involves the use of a boolean array.

Understanding the Problem

Given a string, the task is to identify the first character that does not repeat. For instance, in the string "swiss," the first non-repeated character is "w".

Approach Overview

This algorithm uses two main data structures:

1. Boolean Array: This array will track whether a character has been seen once.
2. Queue (or simply a list for simpler cases): This structure helps maintain the order of characters as they appear in the string so that we can identify the first non-repeated character efficiently.

Key Insight

Characters in the string can be mapped to an index in the boolean array, making it possible to track their presence with a time complexity of $O(1)$. Essentially, boolean flags help determine if a character has been visited and how many times.

Implementation Steps

1. Initialize Structures:
   • Create a boolean array isRepeated of size equal to the character set (for English lowercase letters, use size 26).
   • Use a list (or queue) to keep track of the order of characters.
2. Iterate Through the String:
   • For each character, determine its index in the boolean array. This is usually done by calculating ord(character) - ord('a').
   • If the boolean array at that index is False, check if the character is in the queue:
     • If not, add it to the queue.
     • If it is already in the queue, mark the index in the boolean array true.
   • If the index is already True, continue to the next character.
3. Determine the First Non-Repeated Character:
   • Iterating through the queue will provide the first character that did not have its index marked True in the boolean array.

Here's what an implementation might look like in Python:

1def first_non_repeated(s: str) -> str:
2    # Adjust array size if dealing with more than lowercase English letters
3    is_repeated = [False] * 26
4    from collections import deque
5    char_queue = deque()
6    for char in s:
7        index = ord(char) - ord('a')
8        if not is_repeated[index]:
9            if char in char_queue:
10                is_repeated[index] = True
11            else:
12                char_queue.append(char)
13                
14    while char_queue:
15        char = char_queue.popleft()
16        if not is_repeated[ord(char) - ord('a')]:
17            return char
18    return ''
19
20# Example usage
21print(first_non_repeated('swiss'))  # Output: 'w'

Considerations

Character Set Assumptions

• Memory Usage: The boolean array assumes a fixed character set. For example, using size 256 would handle all extended ASCII characters. This may not be suitable for Unicode without further optimization.

Edge Cases

• Empty String: We need a return strategy for cases with no characters, often an empty string or a custom indicator.
• All Repeated Characters: If every character is repeated, the function appropriately returns an empty result or specified value.

Summary Table

Conclusion

Using a boolean array in combination with a queue offers an efficient $O(n)$ solution to finding the first non-repeated character in a string. By mapping characters to array indices and leveraging the queue to maintain order, this approach adeptly balances time and space complexity. This method can be adapted for diverse character inputs with suitable adjustments to the data structures involved.