First non-repeating character in a string

Find the first non repeating character in string.
Example:
Input : ADBCGHIEFKJLADTVDERFSWVGHQWCNOPENSMSJWIERTFB
Output: K


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Solution 1:
Naive Solution: Use 2 loops to check for every character whether it is non-repeating or not. Return the first such character found.

Linear Solution 1: Use a count array to store the count of every character.
1. Create a count array.
2. Initialize count of every element to 0.
3. Traverse the string once and increment the count of every element found in the string.
4. Traverse the string again and check for the first element for which count is set as 1. Return this element.
5. If not found, return null
If string is large, traversing string again to find first element whose count is 1, is inefficient.

Linear Solution 2 (Optimized): Use index array for storing the index of the string elements.
1. Create an index array.
2. Initialize the index of all index array elements to -1.
3. Traverse the string once and for element of the string, check the value of index of that string element in index array.
   a. If index is -1, it is the first occurrence in the string. Set index[string.charAt(i)] = i
   b. Else, the element is repeating, set index[string.charAt(i)] = -2
4. Traverse the index array once, find the minimum value in the array which is non negative. If found, this is the index of the first non repeating character in the string.
   Else, return null.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Find the first non repeating character in string.
 * Example:
 * Input: ABCDEFGHIJKLADTVDERFSWVGHQWCNOPENSMSJWIERTFB
 * Output: K
 *
 * @author Saurabh
 */
public class FirstNonRepeatingCharacter {
    
    public static Character getFirstNonRepeatingCharacterLinearOptimized(String string) {
        if(string == null || string.length() == 0) {
            return null;
        }
        
        int n = string.length();
        if(n == 1) {
            return string.charAt(0);
        }
        
        int[] charIdx = new int[256];   // Index of non repeating characters. If repeating, then index = -2
        // Initialize character index of all characters to -1
        for(int i = 0; i < 256; i++) {
            charIdx[i] = -1;
        }
        
        for(int i = 0; i < n; i++) {
            if(charIdx[string.charAt(i)] == -1) {
                // character seen first time
                charIdx[string.charAt(i)] = i;
            } else {
                // Repeated character
                charIdx[string.charAt(i)] = -2;
            }
        }
        
        int minIdx = n; // Index of first non repeating character
        for(int i = 0; i < 256; i++) {
            if(charIdx[i] >= 0 && 
                    minIdx > charIdx[i]) {
                minIdx = charIdx[i];
            }
        }
        return (minIdx >= 0 && minIdx < n) ? string.charAt(minIdx) : null;
    }
    
    public static Character getFirstNonRepeatingCharacterLinear(String string) {
        if(string == null || string.length() == 0) {
            return null;
        }
        
        int n = string.length();
        if(n == 1) {
            return string.charAt(0);
        }
        
        int[] charCounts = new int[256];
        // Initialize character counts of all characters to 0
        for(int i = 0; i < 256; i++) {
            charCounts[i] = 0;
        }
        
        for(int i = 0; i < n; i++) {
            charCounts[string.charAt(i)]++;
        }
        
        for(int i = 0; i < n; i++) {
            if(charCounts[string.charAt(i)] == 1) {
                return string.charAt(i);
            }
        }
        return null;
    }
    
    public static Character getFirstNonRepeatingCharacterNaive(String string) {
        if(string == null || string.length() == 0) {
            return null;
        }
        
        int n = string.length();
        for(int i = 0; i < n; i++) {
            boolean flag = true;
            for(int j = 0; j < n; j++) {
                if(i != j && string.charAt(i) == string.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                return string.charAt(i);
            }
        }
        return null;
    }
    
    public static void main(String[] args) {
        String string = "ADBCGHIEFKJLADTVDERFSWVGHQWCNOPENSMSJWIERTFB";
        System.out.println("Output: " + getFirstNonRepeatingCharacterLinearOptimized(string));
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer