Solution with only one pass (C#)


  • 0
    S

    Approach: Single Pass and using 1 Array [Accepted]

    Intuition
    Use an array to store the first occurrence of every character, and store -2 if the character is repeated. Then, determine the min value in the array, that indicates the first occurrence of the unique character. Only 1 scan is needed on the input string.

    Algorithm

    • Create an integer array whose length is the length of our alphabet.

    • Initialize the array elements with values of -1

    • Start scanning the input string one character at a time and check the array element corresponding to the character:

      • if the array element is -1 (that is, this is the first occurrence of the character), set the array element to the index, say i, of the character in the input string.

      • if the array element is a non-negative integer, this means that the character has already occurred in the input string and the value stored in the array element would be the index at which the first time this character occurred. So, set the array element to any negative value, say -2, to indicate that the character has appeared more than once.

      • if the array element is -2, then the character has already appeared more than once. So, ignore / continue.

    • Loop through the array and determine the minimum non-negative number (which represents the index of the first unique character). If all elements are negative, (ie, characters never occurred or occurred more than once), then return -1.

    C#

    public class Solution
    {
            public int FirstUniqChar(string s)
            {
                // Offset index for alphabet characters
                const int OFFSET = 'a';
    
                // Size / number of characters in our alphabet
                const int ALPHABET_SIZE = 26;
    
    
                // Initialize the alphabet array
                int[] alphabet = InitAlphabetArray(ALPHABET_SIZE);
    
    
                // Index of the character in the alphabet array
                int charArrayIndex = 0;
    
                // Loop through the input string, only once :) 
                for (int i = 0; i < s.Length; i++)
                {
                    // Determine the index corresponding to the character
                    charArrayIndex = s[i] - OFFSET;
    
                    // If the corresponding array element of the character has
                    // a value of -1, (ie, this is the first occurrence)
                    if (alphabet[charArrayIndex] == -1)
                        // Set the array element to the index of character
                        alphabet[charArrayIndex] = i;
    
                    // If the corresponding array element of the character has
                    // a non-negative value, (ie, it already occurred before), 
                    else if (alphabet[charArrayIndex] >= 0)
                        // Set the value to -2
                        alphabet[charArrayIndex] = -2;
    
                    else // ie, array element is -2 already,
                        continue;
                }
    
    
                int firstUniqueCharIndex = s.Length;
    
                // Loop through the alphabet array and get the minimum
                // non-negative value, if any.
                foreach (var item in alphabet)
                {
                    if (item >= 0 && item < firstUniqueCharIndex)
                        firstUniqueCharIndex = item;
                }
    
                // if the first unique char index is still the length of the input
                // string, (ie, no unique characters found), return -1. Else, 
                // return the firstUniqueCharIndex value.
                return firstUniqueCharIndex == s.Length ? -1 : firstUniqueCharIndex;
            }
    
            private int[] InitAlphabetArray(int size)
            {
                int[] alphabet = new int[size];
    
                for (int i = 0; i < alphabet.Length; i++)
                    alphabet[i] = -1;
    
                return alphabet;
            }
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(s) + O(a) = O(s+a) = O(n)$$, where $$O(s)$$ is the time needed to scan all elements of the input string s, and $$O(a)$$ is the time needed to scan alphabet array elements.

    • Space complexity: $$O(1)$$


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.