ゼロから始めるLeetCode Day76「3. Longest Substring Without Repeating Characters」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day75 「15. 3Sum」

今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！

問題

3. Longest Substring Without Repeating Characters
難易度はMedium。

問題としては、文字列が与えられたとき、文字を繰り返さずに最長の部分文字列の長さを求めなさいというものです。

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.

解法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic,length,start = {},0,0
        for i,j in enumerate(s):
            if j in dic:
                sums = dic[j] + 1
                if sums > start:
                    start = sums
            num = i - start + 1
            if num > length:
                length = num
            dic[j] = i
        return length
# Runtime: 60 ms, faster than 76.33% of Python3 online submissions for Longest Substring Without Repeating Characters.
# Memory Usage: 13.9 MB, less than 55.58% of Python3 online submissions for Longest Substring Without Repeating Characters.

lengthで最大の長さを保持し、startで部分文字列の開始位置を保持しています。

そこまで書くことはないですね・・・

そういえば組み込み関数が便利っていうのはPython特有なのでしょうか？
言語によっては組み込み関数によって実装が楽だったりするとかありそうですが・・・・

他の言語で解いてみるのも面白いのでJavaで書いたりもたまにしていますがなかなか慣れないものですね。

では今回はここまで。
お疲れ様でした。