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:
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;
}
}