Title:

First Unique Character in a String - Startegy 1

Link to LeetCode:

https://leetcode.com/problems/first-unique-character-in-a-string/

Specification:

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

Example 1:

s = "leetcode"
return 0.

Example 2:

s = "loveleetcode",
return 2.

Initial Code and Signature:


public interface FirstUniqueChar {
	
	public int firstUniqChar(String s) ;

}

Algorithm:

  1. Consider three arrays. One stores unique chars, the other stores the frequency of the chars, and the last one stores the first appearances.
  2. Count the frequency of each char in the string and put into the frequency array.
  3. Update first appearance array if the char is seen for the first time.
  4. Scan the char array and return the first char with frequency one and minimum first appearance.

Run-Time Complexity Analysis

GitHub Project:

https://github.com/m-h-s/Algorithms-Codes/tree/master/34-FirstNonRepeatingChar

Code:


/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 06 - 03
 *  
 * License Creative Commons
 * 
 * Copyright by Mahsa Sadi
 *
 */
public class FirstUniqueCharS1 implements FirstUniqueChar {

	/**
	 * 
	 * Problem:
	 * First Unique Char in a String
	 * 
	 * 
	 * Description:
	 * Given a string, find the first non-repeating character in it and return it's index. 
	 * If it doesn't exist, return -1.
	 * 
	 * 
	 * Solution:
	 * 1- Consider three arrays. One stores unique chars, the other stores the frequency of the chars, and the third one stores the index of first appearance.
	 * 2- Update the first apperance if the char is seen for the first time.
	 * 2- Count the frequency of each char in the string and put into the two above array.
	 * 3- Scan the char array and return the first char with frequency one and minimum first appearance.
	 */
	 
	@Override
	public int firstUniqChar(String s) {

		int uniqueIndex = -1;

		if (s.length () > 0)
		{

			char [] chars = new char [s.length ()];
			int [] counts = new int [s.length ()];
			int [] firstIndices  =  new int [s.length ()];
			int lastIndex = 0;



			for (int i = 0; i < s.length (); i++ )
			{
				boolean found = false;
				int j = 0;

				while (j < s.length () && !found)
				{
					if (s.charAt(i) == chars [j])
					{ 
						counts [j] ++;
						found = true;
					}

					j++;
				}


				if ( !found )
				{
					chars [lastIndex] = s.charAt(i);
					counts [lastIndex] = 1;
					firstIndices [lastIndex] = i;
					lastIndex++;
				}

			}


			for (int i = 0; i <= lastIndex; i++ )
			{
				if (counts [i] == 1)
				{

					uniqueIndex = firstIndices [i];
					break;
				}
			}
		}


		return uniqueIndex;
	}

}