Longest substring without repeated characters

Problem:

Given a string, find the longest substring without repeated characters.
For example: given string "abbcrqmppaq" the output should be "bcrqmp"

Solution:

We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).

We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.

If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.

Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.

import java.util.*;
class FindLongestSubString {

  //abbcprqmpaq
  private static String getLongest(String word) {
    //sliding window, advance start index and end index
    Map<Character, Integer> nextPos = new HashMap<>();
    int maxLength = 0;
    int startIndex = 0;
    for(int start = 0, end = 0; end < word.length(); end++) {  //end = 10q
      if(nextPos.containsKey(word.charAt(end))) {
        start = Math.max(start, nextPos.get(word.charAt(end)));  //7
      }
      if(end - start + 1 > maxLength) {    //6
          maxLength = end - start + 1;    //6
          startIndex = start;  //2
      }
      nextPos.put(word.charAt(end), end + 1);  //a10;b3;c4;p9;r6;q11;m8
    }
    return word.substring(startIndex, startIndex + maxLength);
  }
  public static void main(String...args) {
    String result = getLongest("abbcprqmpaq");
    System.out.println(result);
    result = getLongest("abbcprqmpaqx");
    System.out.println(result);
    result = getLongest("abbcrqmppaqx");
    System.out.println(result);
    result = getLongest("abbcprqmpazx");
    System.out.println(result);
    result = getLongest("mznhieabbcprqmpazx");
    System.out.println(result);
  }
}

The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap