Longest Substring Without Repeating Characters[M]

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

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.

Example 2:

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.

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

---

1. Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        temp = ""
        cnt = 0

        for x in s:
            if x not in temp:
                temp += x
                if len(temp) > cnt:
                    cnt = len(temp)
            else:
                idx = temp.index(x)
                temp = temp[idx+1:]
                temp += x
        return cnt

- 뭐 어찌어찌 풀긴 했는데, else 부분에서 test case를 통과 못하는 경우가 있었다.

예를 들어 s = "dsdf"의 경우 두번 째 d가 나왔을 때, 앞선 문자중 s까지는 살려서 다시 counting을 들어갔어야 했지만 나는 처음에 중복문자가 나오면 지금까지 저장했던 놈들을 아예 초기화하는 걸로 코드를 짰었다.

 

이게 릿코드에서 어떤 test case에서 막혔는지까지 알려줘서 디버깅이 가능했는데,

 

test case 뭐가 fail인지도 알려주지 않으면 디버깅하는데 애를 좀 먹을 거 같다 ;;

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        q = deque()
        for c in s:
            if c in q:
                while q.popleft() != c :
                    continue
            q.append(c)
            ans = max(ans,len(q))
        return ans

 

이렇게 python deque를 이용해서도 간편하게 풀 수 있다.

 

2. C

- 도저히 답이 안나와서 GPT좀 돌렸다. 와나 C로 String 문제 어떻게 푸나 진짜.. 답지를 봤는데 생각의 차원이 다르다. 굉장히 불편하네.. String이라는 놈을 조각조각 분해해서 문제를 푸는 느낌-_- 아오!!!!

 

"a s d f g h j f a " <= test code 예시

int lengthOfLongestSubstring(char* s) {
    int n = strlen(s);
    if(n==0) return 0;

    int idx[128] = {0}; //ASCII 문자 수만큼 크기 설정
    int maxL = 0;
    int start = 0;

    for(int end=0; end < n ; end++){
        char currentChar = s[end];

        if(idx[currentChar]>0){
            start = idx[currentChar] > start ? idx[currentChar] : start;
        }

        int length = end-start+1;
        maxL = length > maxL ?  length : maxL;

        idx[currentChar] = end+1;
    }
    return maxL;

}

 

이거 진짜 어떻게 생각해내냐..

 

 

3. C++

 

걍 뭐,, C와 거의 똑같이 코딩했다.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int n = s.length();
        if(n==0) return 0;

        unordered_map<char,int> m;
        int start = 0;
        int ans = 0;

        for(int i=0;i<n;i++){
            char c = s[i];

            if(m[c]!=NULL){
                start = m[c] > start ? m[c] : start;
            }

            int len = i-start+1;

            ans = len > ans ? len : ans;
            m[c] = i+1;
        }
        return ans;


    }
};