CODEWITHSUNDEEP
javabig-o
valik
valik

Reputation: 2094

Finding first non repeating character in a string in relation to Big O

I solved a task concerning finding the first non-repeating character. For example, given the input "apple" the answer would be "a", the first character that isn't repeated. Even though "e" is not repeated it's not the first character. Another example: "lalas" answer is "s".

public static char firstNonRepeatingCharacter(String input) {
    boolean unique;
    int count = input.length();
    char[] chars = input.toCharArray();
    for (int i = 0; i < input.length(); i++) {
        unique = true;
        for (int j = 0; j < input.length(); j++) {
            count--;
            char c = chars[i];
            if (i != j && c == chars[j]) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return input.charAt(i);
        }
    }
    return (0);
}

I want to simplify this code due to the nested loop having O(n2) complexity. I have been looking at the code trying to figure out if i could make it any faster but nothing comes to mind.

Upvotes: 2

Views: 592

Answers (4)

Kunal
Kunal

Reputation: 51

private static int Solution(String s) {
        
        // to check is values has been considered once
        Set<String> set=new HashSet<String>(); 
        
        // main loop
        for (int i = 0; i < s.length(); i++) {
            String temp = String.valueOf(s.charAt(i));

            //rest of the values
            String sub=s.substring(i+1);
                if (set.add(temp) && !sub.contains(temp)) {
                    return i;
                }
        }
        return -1;
    }

Upvotes: 0

Praveen
Praveen

Reputation: 1881

Another way is to find the first and last indexOf the character. If both are same then it is unique.

public static char firstNonRepeatingCharacter(String input) {
    for(char c:input.toCharArray())
        if(input.indexOf(c) == input.lastIndexOf(c))
            return c;
    return (0);
}

EDIT:

Or with Java 8+

return (char) input.chars()
                   .filter(c -> input.indexOf(c) == input.lastIndexOf(c))
                   .findFirst().orElse(0);

Upvotes: 2

tksilicon
tksilicon

Reputation: 4426

See this solution. Similar to the above @Lucbel. Basically, using a LinkedList. We store all non repeating. However, we will use more space. But running time is O(n).

import java.util.LinkedList;
import java.util.List;

public class FirstNone {

    public static void main(String[] args) {

        System.out.println(firstNonRepeatingCharacter("apple"));
        System.out.println(firstNonRepeatingCharacter("potatoaonionp"));
        System.out.println(firstNonRepeatingCharacter("tksilicon"));

    }

    public static char firstNonRepeatingCharacter(String input) {

        List<Character> charsInput = new LinkedList<>();

        char[] chars = input.toCharArray();

        for (int i = 0; i < input.length(); i++) {

            if (charsInput.size() == 0) {
                charsInput.add(chars[i]);

            } else {

                if (!charsInput.contains(chars[i])) {
                    charsInput.add(chars[i]);
                } else if (charsInput.contains(chars[i])) {

                    charsInput.remove(Character.valueOf(chars[i]));
                }
            }

        }

        if (charsInput.size() > 0) {
            return charsInput.get(0);

        }
        return (0);
    }
}

Upvotes: 0

Lucbel
Lucbel

Reputation: 339

O(n) is better.

Use an intermedian structure to handle the number of repetitions.

public static char firstNonRepeatingCharacter(String input) {
    boolean unique;
    int count = input.length();
    char[] chars = input.toCharArray();
    for (int i = 0; i < input.length(); i++) {
        unique = true;
        for (int j = 0; j < input.length(); j++) {
            count--;
            char c = chars[i];
            if (i != j && c == chars[j]) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return input.charAt(i);
        }
    }
    return (0);
}

public static char firstNonRepeatingCharacterMyVersion(String input) {
    Map<String,Integer> map = new HashMap();
    // first iteration put in a map the number of times a char appears. Linear O(n)=n
    for (char c : input.toCharArray()) {
        String character = String.valueOf(c);
        if(map.containsKey(character)){
            map.put(character,map.get(character) + 1);
        } else {
            map.put(character,1);
        }
    }
    // Second iteration look for first element with one element.
    for (char c : input.toCharArray()) {
        String character = String.valueOf(c);
        if(map.get(character) == 1){
            return c;
        }
    }
    return (0);

}




    public static void main(String... args){
    System.out.println(firstNonRepeatingCharacter("potatoaonionp"));
    System.out.println(firstNonRepeatingCharacterMyVersion("potatoaonionp"));

}

Upvotes: 1

Related Questions