[리트코드] 3. Longest Substring Without Repeating Characters

문제 :

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

Longest Substring Without Repeating Characters - LeetCode

 

난이도 : Medium

 

풀이 방법 : 브루트 포스 O(n^2)

 

문자열 s에서 중복되는 문자 없이 가장 긴 서브 스트링을 찾는 문제였다. 

슬라이딩 윈도우 방식을 사용하면 O(n) 만큼으로도 해결 할 수 있다고 한다. 리트코드에 토픽 보는 방법을 몰라 풀리는 대로 풀었는데 이제는 좀 효율적을 푸는 방법도 같이 공부해야겠다 하하 

 

c++ 코드 (브루트포스)

class Solution {
public:
    string answer = "";
    int answerLength = 0;

    
    int lengthOfLongestSubstring(string s) {
        
        if(s.length() == 1){
            return 1;
        }
        
        for(int i = 0; i< s.length(); i++){
            for(int j = i; j < s.length(); j ++){
                char findCharacter = s[j];
                 if(answer.find(findCharacter) == -1){ // can not find
                    answer += findCharacter;
                }else {
                   if(answerLength < answer.length()){
                        answerLength = answer.length();
                        }  
                     answer = "";
                    break;
                    }
                    
                }
            }
        return answerLength;
        }
    };

 

c++ 슬라이딩 윈도우 방식 

: 풀어볼 예정

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        //SLIDING WINDOW  - TIME COMPLEXITY O(2n)
        //                  SPACE COMPLEXITY O(m)   //size of array
        
        int store[256]={0}; //array to store the occurences of all the characters
        int l=0;    //left pointer
        int r=0;    //right pointer
        int ans=0;  //initializing the required length as 0
        
        while(r<s.length())     //iterate over the string till the right pointer reaches the end of the string 
        {
            store[s[r]]++;      //increment the count of the character present in the right pointer 
            
            while(store[s[r]]>1)    //if the occurence become more than 1 means the char is repeated
            { 
                store[s[l]]--;   //reduce the occurence of temp as it might be present ahead also in the string
                l++;         //contraction of the present window till the occurence of the 't' char becomes 1
            }
            
            ans = max(ans,r-l+1);    //As the index starts from 0 , ans will be (right pointer-left pointer + 1)
            r++;        // now will increment the right pointer 
        }
        return ans;
    }
};