【LeetCode】3.Longest Substring Without Repeating Characters 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：Python, two pointer
2. 解答2：Rust
補足・参考・感想

問題

原文

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

Example 1:

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

1
2
3

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

Example 2:

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

1
2
3

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

Example 3:

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.

1
2
3
4

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.

Constraints:

0 <= s.length <= 5 * 10⁴

s consists of English letters, digits, symbols and spaces.

内容

文字列sが与えられます。最大部分文字列を見つけてください。

例3： s = “pwwkew”

“wke”が最大部分文字列であり、その長さは3です。

“pwke”は各要素の場所を変えてしまっているのでだめなようです。

※正しくない可能性があります。

方針

前提

・2つのポインタを使う

・それぞれのポインタは文字列sにおける部分文字列の左端と右端を指すインデックス

※左右のインデックスの差が部分文字列の長さを表す

実装のイメージ

・文字列s内の各文字を全探索する

・各文字が初出現の要素である限り右のポインタを右に伸ばし続ける

・既出要素がある場合で、その既出要素が左右のポインタの外側にある場合は右のインデックスを右に伸ばし続ける

・既出要素がある場合で、その既出要素が左右のポインタの内側にある場合は、左ポインタを右ポインタの右隣りに変更する

イメージ　※赤が左、青が右ポインタ

まずは左右のポインタを広げていく

a b c b b c a c

a b c b b c a c　※bは既出(2文字目)なので、左ポインタを移動。

a b c b b c a c　※左ポインタを最初のbの右隣りにして再スタート

同時に、2つ目のb(青色のb)の位置を記録

a b c b b c a c　※bは既出(4文字目)なので、左ポインタを移動。

a b c b b c a c　※左ポインタは2つ目のbの位置の右隣になり、再スタート

a b c b b c a c

↑このように最後まで繰り返して左右のポインタの幅が最大だった時の値を返す。

解答

解答1：Python, two pointer

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #出現済み要素をキー、そのインデックスを値として保持する辞書
        seen = {}
        #文字列sの左側のポインタとして使うインデックス
        left = 0
        #最大部分文字列の長さを保持する変数
        output = 0
        #文字列sを全探索。rightは文字列sの右側のポインタとして使うインデックスでもある
        for right in range(len(s)):
            #right番目の要素が初出現の場合
            if s[right] not in seen:
                #現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入
                output = max(output,right-left+1)
            #right番目の要素が既出の場合
            else:
                #既出要素(right番目の要素)の出現場所(インデックス)が左側のポインタleftの場所(インデックス)より小さい場合
                #つまり、left～rightの中に既出の要素がない場合
                if seen[s[right]] < left:
                    #現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入
                    output = max(output,right-left+1)
                #既出要素がleft～rightの中にある場合は、left(インデックス)を既出要素(right番目の要素)の右隣りに移動
                else:
                    left = seen[s[right]] + 1
            #right番目の要素は、その要素をキー、その出現位置(インデックス)を値として辞書seenに代入
            seen[s[right]] = right
        #outputを返す
        return output

class Solution:

def lengthOfLongestSubstring(self, s: str) -> int:

#出現済み要素をキー、そのインデックスを値として保持する辞書

seen = {}

#文字列sの左側のポインタとして使うインデックス

left = 0

#最大部分文字列の長さを保持する変数

output = 0

#文字列sを全探索。rightは文字列sの右側のポインタとして使うインデックスでもある

for right in range(len(s)):

#right番目の要素が初出現の場合

if s[right] not in seen:

#現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入

output = max(output,right-left+1)

#right番目の要素が既出の場合

else:

#既出要素(right番目の要素)の出現場所(インデックス)が左側のポインタleftの場所(インデックス)より小さい場合

#つまり、left～rightの中に既出の要素がない場合

if seen[s[right]] < left:

#現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入

output = max(output,right-left+1)

#既出要素がleft～rightの中にある場合は、left(インデックス)を既出要素(right番目の要素)の右隣りに移動

else:

left = seen[s[right]] + 1

#right番目の要素は、その要素をキー、その出現位置(インデックス)を値として辞書seenに代入

seen[s[right]] = right

#outputを返す

return output

・時間計算量O(n)

nは文字列sの文字数。leftポインタを更新しながら進むので、1巡するだけで良い。

・空間計算量O(m)

mは重複を除外した文字列s内の文字数。

各文字の出現位置を記録するハッシュテーブル(辞書)を記録する必要があるので、ｍ文字分の記憶領域が必要

解答2：Rust

use std::cmp::max;
use std::collections::HashMap;
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut m = HashMap::new();
        let mut ans = 0;
        let mut before = -1;
        let mut current = 0;
        for c in s.chars() {
            if let Some(last) = m.insert(c, current) {
                before = max(before, last);
            }
            ans = max(ans, current - before);
            current += 1;
        }
        ans
    }
}

use std::cmp::max;

use std::collections::HashMap;

impl Solution {

pub fn length_of_longest_substring(s: String) -> i32 {

let mut m = HashMap::new();

let mut ans = 0;

let mut before = -1;

let mut current = 0;

for c in s.chars() {

if let Some(last) = m.insert(c, current) {

before = max(before, last);

}

ans = max(ans, current - before);

current += 1;

}

ans

}

写経

補足・参考・感想

参考

自分が後で見返して理解しやすいように、ツールを使って図解しつつ、記事に組み込めるようにしたい。

前：704. Binary Search

次：12. Integer to Roman

LeetCode 解答・解説記事一覧