Naive Solution

A brute force approach would involve iterating through the string for each character to check if it repeats. For each character, we would iterate through the rest of the string to see if the same character appears again. If it doesn't, we've found our first non-repeating character.

Code (Python):

def first_unique_char_brute_force(s):
    for i in range(len(s)):
        is_unique = True
        for j in range(len(s)):
            if i != j and s[i] == s[j]:
                is_unique = False
                break
        if is_unique:
            return i
    return -1

Time Complexity: O(n^2), where n is the length of the string. Space Complexity: O(1), as we use only a constant amount of extra space.

Optimal Solution

We can optimize this by using a hash map (dictionary in Python) to store the frequency of each character. Then, we can iterate through the string once more to find the first character with a frequency of 1.

Code (Python):

def first_unique_char(s):
    char_counts = {}
    
    # Count character frequencies
    for char in s:
        char_counts[char] = char_counts.get(char, 0) + 1
    
    # Find the first unique character
    for i, char in enumerate(s):
        if char_counts[char] == 1:
            return i
    
    return -1

Explanation:

1. Count Frequencies: The first loop iterates through the string s and counts the occurrences of each character, storing them in the char_counts dictionary.
2. Find First Unique: The second loop iterates through the string s again, this time checking the frequency of each character in the char_counts dictionary. If a character has a frequency of 1, it means it's unique, and we return its index.
3. Handle No Unique Characters: If the loop completes without finding any unique characters, we return -1.

Time Complexity: O(n), where n is the length of the string. This is because we iterate through the string twice.

Space Complexity: O(1). The size of the hash map will be, at most, the number of unique characters in the string. Since the string consists of lowercase English letters, the hash map can contain at most 26 key-value pairs, making the space complexity constant.

Edge Cases

• Empty String: Although the constraints state that the string length is at least 1, it's good to consider the case where the string is empty. The code handles this case correctly by returning -1 because the loop will not execute.
• String with all repeating characters: The code correctly handles the case where no unique characters are present by returning -1 after iterating through the entire string.
• Very Long String: The solution should scale well for very long strings due to the linear time complexity.