Finding the first non-repeated character of a string in O(n) using a boolean array?

Question

My question is related to this earlier question

Find the first un-repeated character in a string.

In one of my interviews I was asked to write a function to determine the first unique character in a string in time O(n) using as extra space only a boolean array of length n. That is, find the first non repeating letter in a string using only O(n) complexity and a bool array of length n. Can some suggest how to solve it with bool array?

Answer 1

Well, if the size of the character set is constant... Say, for instance, 0-255...

Scan the string looking for character 0.

Then scan the string looking for character 1.

Then scan the string looking for character 2.

...

Finally, scan the string looking for character 255.

This takes 256*n operations which is O(n).

During each scan, if the character is unique, mark its position in the bitmap. At the end return the character at the first marked position. (Or just record the first unique character and its location using k + log(n) bits. Use a hard-coded lookup table or whatever for very small n; otherwise, n bits is generous.)

Although somehow I suspect this is not what the interviewer had in mind.

Answer 2

    private static void FirstNonRepeatingCharacters()
    {
        string s = "abbazccdde";
        var result = from item in s
                     group item by item into groupedItems
                     where groupedItems.Count() == 1
                     select groupedItems.Key;
        Console.WriteLine(result.First());                    
    }

C# implementation

Answer 3

For Single Pass Solution

Maintain 2 data structures:

1. Array / bitmap / hashtable for tracking the count of each character
2. LinkedHashMap to track the characters which have occured only once so far.

LinkedHashMap has

• O(1) insertion
• O(1) deletion

• O(1) search

  class Node
  {
    char data;
    Node next;
    Node prev;
  };
  
  class LinkedHashMap
  {
          // This will keep the insertion order intact
          Node listHead;
          Node currentTail = listHead;
          HashTable<char, Node> charExistsMap;
  
      void Add(char ch) 
      {
          if(!charExistsMap.ContainsKey(ch)) 
          {
              // Add to both hashtable and linkedlist
              Node n = new Node(ch);
              n->next = null;
              n->prev = curentTail; // Added To List
              currentTail = n;
              charExistMap.Add(ch, n);
          }
          else 
          {
              // Remove from both hashtable and linkedlist
              Node n = charExistMap.Remove(ch);
              if(n->prev != null) 
              {
                  n->prev->next = n->next
                  listHead = n->next; // update head
              }
              if(n->next != null)
                  n->next->prev = n->prev;
           }
      }
  
      char GetFirstNonRepeatingChar()
      {
          return listHead->data;
      }
  

  }

After the original string is traversed, the head of the LinkedHashMap will contain the first character which is not repeated.

Answer 4

public class FirstUniqueChar {

  public static void main(String[] args) {

    String test = "ABxacd";

    test = test.toUpperCase();
    for (int i = 0; i < test.length(); i++) {
        int firstIndex = test.indexOf(test.charAt(i));
        int lastIndex = test.lastIndexOf(test.charAt(i));
        if (firstIndex == lastIndex) {
            System.out.println("First unique char of String " + test.charAt(i));
            break;
        }

    }

  }
}

Answer 5

Do that in two passes:

1st pass: create bool array of size 256 and for each char in the text mark the element of index int(that char). This takes O(n).

2nd pass: for each char in the text check if the corresponding array element is marked. If not then you found your answer. This also takes O(n).

Answer 6

Have two boolean arrays, seenOnce and seenMany. Loop over the string populate the arrays. Loop over the string again checking if the character is in seenFirst but not in seenMany. If it is thats your first non-repeating character.

Here's some example code in python.

subject = "ttojxxlma"

seenOnce = [False for i in range(256)]
seenMany = [False for i in range(256)]

for c in subject:
    index = ord(c)
    if seenOnce[index] == False:
        seenOnce[index] = True
    else:
        seenMany[index] = True

for c in subject:
    index = ord(c)
    if seenOnce[index]==True and seenMany[index] != True:
        print(c)
        break

Ok that still uses too boolean array (or python lists =P). To use only one array you can have one array thats double the amount of characters. Instead of accessing the second array double the index and access the big one. But thats just messy.

Not sure if it can be done with less space.