Java – what is the best way to find the first repeating character in a string

I wrote the following code to detect the first duplicate character in the string

public static int detectDuplicate(String source) {
    boolean found = false;
    int index = -1;
    final long start = System.currentTimeMillis();
    final int length = source.length();
    for(int outerIndex = 0; outerIndex < length && !found; outerIndex++) {
        boolean shiftPointer = false;
        for(int innerIndex = outerIndex + 1; innerIndex < length && !shiftPointer; innerIndex++ ) {
            if ( source.charAt(outerIndex) == source.charAt(innerIndex)) {
                found = true;
                index = outerIndex;
            } else {
                shiftPointer = true;
            }
        }
    }
    System.out.println("Time taken --> " + (System.currentTimeMillis() - start) + " ms. for string of length --> " + source.length());
    return index;
}

I need help with two things:

>What is the worst-case complexity of this algorithm My understanding is O (n). > Is this the best way? Can anyone provide a better solution (if any)?

Thanks, NN

Solution

As others mentioned, your algorithm is O (n ^ 2) This is an O (n) algorithm because HashSet #add runs for a constant time (the hash function disperses the elements correctly in the bucket) – note that I initially resized the hash set to the maximum size to avoid resizing / re hashing:

public static int findDuplicate(String s) {
    char[] chars = s.tocharArray();
    Set<Character> uniqueChars = new HashSet<Character> (chars.length,1);
    for (int i = 0; i < chars.length; i++) {
        if (!uniqueChars.add(chars[i])) return i;
    }
    return -1;
}

Note: this returns the index of the first copy (that is, the index of the first character that repeats the previous character) To return the index of the first occurrence of this character, you need to store the index in map < character, integer > (in this case, map #put is also o (1)):

public static int findDuplicate(String s) {
    char[] chars = s.tocharArray();
    Map<Character,Integer> uniqueChars = new HashMap<Character,Integer> (chars.length,1);
    for (int i = 0; i < chars.length; i++) {
        Integer prevIoUsIndex = uniqueChars.put(chars[i],i);
        if (prevIoUsIndex != null) {
            return prevIoUsIndex;
        }
    }
    return -1;
}