[알고리즘] Longest Substring Without Repeating Characters

포인트

1. 중복 문자가 없는 가장 긴 부분 문자열의 길이를 반환을 하는 방법

2. 딕셔너리를 하나 만들고 인덱스를 넣어가면서 지속적으로 업데이트? 하는 방법이 있을 것 같다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
  int lengthOfLongestSubstring(string s)
  {
    unordered_map<char, int> used; // 해시를 하나 지정을 해준다

    int start = 0;
    int max_length = 0;

    for (auto i = 0; i < s.size(); i++) //char 를 돌면서
    {
      char ele = s[i];
      if (used.find(ele) != used.end() && start <= used[ele]) // 해시 안에 있고 start 가 짧다면
      {
        start = used[ele] + 1; // start 갱신
      }
      else // 아니면
      {
        max_length = max(max_length, i - start + 1); //max 값 갱신
      }
      used[ele] = i; //index를 넣어준다.
    }
    return max_length; // 최댓값 반환
  }
};

python

# 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ele1 = {}
        start = 0
        max_length = 0

        for index, char in enumerate(s):
            # 이미 등장 했던 문자라면 start 를 갱신하고 새로 시작
            if char in ele1 and start <= ele1[char]:
                start = ele1[char]+1
            else:
                #  아니면 길이를 늘려준다
                max_length = max(max_length, index-start+1)

            # 현재 문자 위치를 삽입
            ele1[char] = index

        return max_length