Skip to content

Instantly share code, notes, and snippets.

@adnan-SM
Created April 29, 2020 06:43
Show Gist options
  • Save adnan-SM/07497c1f2859b74d4e1fd5d30efa63a5 to your computer and use it in GitHub Desktop.
Save adnan-SM/07497c1f2859b74d4e1fd5d30efa63a5 to your computer and use it in GitHub Desktop.
Longest Substring Problem
class NoRepeatSubstring {
public static int findLength(String str) {
int windowStart = 0, maxLength = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
// try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char rightChar = str.charAt(windowEnd);
// if the map already contains the 'rightChar', shrink the window from the beginning so that
// we have only one occurrence of 'rightChar'
if (charIndexMap.containsKey(rightChar)) {
// this is tricky; in the current window, we will not have any 'rightChar' after its previous index
// and if 'windowStart' is already ahead of the last index of 'rightChar', we'll keep 'windowStart'
windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
}
charIndexMap.put(rightChar, windowEnd); // insert the 'rightChar' into the map
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // remember the maximum length so far
}
return maxLength;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment