3. Longest Substring Without Repeating Characters

Leetcode Hash Table Two Pointers String

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析

滑动窗口题，类似于LeetCode 76. Minimum Window Substring。

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length();

    // 哈希表
    int[] map = new int[128];

    // 左右指针 
    int l = 0, r = 0;

    // 最长子字符串
    int maxLength = 0;

    // 左右字符
    char cr, cl;
    while (r < n) {
        cr = s.charAt(r);
        map[cr]++;
        // 子字符串不重复，满足要求
        if (map[cr] == 1) {
            // 子字符串长度是否比目前发现的最长字符串还长？
            if (r - l + 1 > maxLength)
                maxLength = r - l + 1;
        } else {
            // 移动左指针，直到不重复
            while (true) {
                cl = s.charAt(l);
                map[cl]--;
                l++;
                if (cl == cr) break;
            }
        }
        r++;
    }
    return maxLength;
}