Blind 75
Longest Substring Without Repeating Characters
- Problem
- LC 3
- Category
- String
- File
- blind75_LC3LongestSubstringWithoutRepeating.java
- Path
- pkg5leetcode/blind75/blind75_LC3LongestSubstringWithoutRepeating.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC3LongestSubstringWithoutRepeating.java
- Approach
- Sliding window with last-seen index map.
- Complexity
- Time O(n), Space O(min(n, alphabet))
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Longest Substring Without Repeating Characters | LC 35 * APPROACH: Sliding window with last-seen index map.6 * COMPLEXITY: Time O(n), Space O(min(n, alphabet))7 */8import java.util.*;9 10public class blind75_LC3LongestSubstringWithoutRepeating {11 static int lengthOfLongestSubstring(String s) {12 Map<Character, Integer> last = new HashMap<>();13 int best = 0, left = 0;14 for (int right = 0; right < s.length(); right++) {15 char c = s.charAt(right);16 if (last.containsKey(c) && last.get(c) >= left) left = last.get(c) + 1;17 last.put(c, right);18 best = Math.max(best, right - left + 1);19 }20 return best;21 }22 23 public static void main(String[] args) {24 check(lengthOfLongestSubstring("abcabcbb") == 3, "case1");25 check(lengthOfLongestSubstring("bbbbb") == 1, "case2");26 System.out.println("all tests passed");27 }28 29 static void check(boolean cond, String name) {30 if (!cond) throw new AssertionError("FAILED: " + name);31 System.out.println(" PASS " + name);32 }33}