跳轉到

3. Longest Substring

題目大意

給定一個字串 s，找出其中不包含重複字元的最長子字串長度。

範例一
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
範例二
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
範例三
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

題目原文連結

約束條件

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、數字、符號和空格組成。

解題想法

  • 把兩個指標都放在字串的開頭。
  • 向右移動結尾指標，直到遇到重複的字元。
  • 如果遇到重複的字元，就把開頭指標移動到重複字元的後面。
  • 重複步驟 2 和 3，直到結尾指標到達字串的末尾。
  • 在移動結尾指標的過程中，記錄最長的子串長度。

<?php
function lengthOfLongestSubstring($s) {
  // 獲取字串的長度
  $char_len = strlen($s);

  //初始化一個數組來儲存字元及其最後一次出現的索引
  $char_index = [];

  // 初始化左指標，代表當前考慮的子串的起始位置
  $left = 0;

  // 初始化最長子串的長度
  $maxLength = 0;

  // 遍歷字串中的每個字元
  for ($right = 0; $right < $char_len; $right++) {
    // 獲取當前字元
    $char = $s[$right];

    // 如果當前字元已經出現過，並且上一次出現的位置在當前視窗的左邊界或更右
    if (array_key_exists($char, $char_index) && $char_index[$char] >= $left) {
      // 更新左指標為當前字元上次出現位置的下一位，以排除重複字元
      $left = $char_index[$char] + 1;
    }

    // 更新或添加當前字元的索引到陣列中
    $char_index[$char] = $right;

    // 計算當前無重複字元子串的長度，並更新最長長度
    $maxLength = max($maxLength, $right - $left + 1);
  }

  // 返回最長無重複字元子串的長度
  return $maxLength;
}