LeetCode - 3

Longest Substring Without Repeating Characters

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

思路：

• 使用HashMap存储字符及其位置，key为字符，value为字符出现的位置;

• 使用start记录子字符串的起始位置;

• 使用max记录符合条件的子字符串的最大长度：max = Math.max(max, index - start + 1);

• 遍历字符串中的每个字符，用index记录位置，取到每个字符s.charAt(i)，先判断HashMap中是否已存在此字符;

• 如果不存在此字符则将其存入HashMap:
  例如字符串abcda，HashMap中依次存入(a, 0)、(b, 1)、(c, 2)、(d, 3).

• 如果存在此相同字符:
  1、说明已找到一个符合条件的子字符串（起始位置为start，终止位置为index的上一个位置）;
  例如字符串abcdaea，找到第五个字符a为已存在字符，则找到符合条件的子字符串为abcd;
  例如字符串abcddea，找到第五个字符d为已存在字符，则找到符合条件的子字符串为abcd.
  2、在HashMap中找到此字符的value值(也就是位置)，记为p，更新子字符串的起始start位置：如果start >= p + 1，则仍保留start位置，否则更新start = p + 1;
  例如字符串abcddea，找到相同字符d，第一次出现位置为3，start值为0，则应更新start为4.
  例如字符串abcdaea，找到相同字符a，第一次出现位置为0，start值为0，则应更新start为1.
  3、更新此字符在HashMap中的value值，即更新它的位置.

• 遍历结束后，返回max的值.

• 实现代码

  public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    for (int index = 0, start = 0; index < s.length(); ++ index) {
        if (map.containsKey(s.charAt(index))) {
            start = Math.max(start, map.get(s.charAt(index)) + 1);
        }
        map.put(s.charAt(index), index);
        max = Math.max(max, index - start + 1);
    }
    return max;
  }