Can someone help me calculate big O? c++


  • 0
    J

    I'm only advancing the right side of the window by 1 or more places every iteration. So I was thinking my solution is O(n) but then I grow the window X amount of times depending on how many palindromes are found so O(2n). Can someone explain the big O for my solution, thanks!

    class Solution {
            public:
                    string longestPalindrome(string s) {
                            if(s.size() < 2)
                            {
                                    return s;
                            }
    
                            int eos = s.size() - 1; // end of string
    
                            int r(0), l(0), loc(0), size(0); //right and left window, substring location, substring size
                            for(r = l + 1; r < s.size(); l = r++){
                                    if(s[l] == s[r] || (l > 0 && s[l-1] == s[r])) //palindrom test for aa or aba
                                    {
                                            if(s[l] != s[r]) //assume aba type palindrom found
                                            {
                                                    l--;
                                            } else {
                                                //find multiples in a row aaa, aaaaa, aaaaaa
                                                while(r < eos && s[l] == s[r + 1]){
                                                    r++;
                                                }
                                            }
    
    
                                            //find size of palindrom by growing window in both directions
                                            while(l > 0 && r < eos && s[l-1] == s[r+1])
                                            {
                                                    l--;
                                                    r++;
                                            }
    
                                            //if found palindrom bigger than current, record it's place
                                            if(r-l+1 > size)
                                            {
                                                    size = r-l+1;
                                                    loc = l;
                                            }
    
                                            //if found palindrom is bigger than 2, reset right to halfway
                                            //between left and right side of the window
                                            if(r-l > 2){
    
                                                    r =  1+r-((r-l)/2);
                                            }
                                    }
                            }
    
                            return size > 0 ? s.substr(loc,size) : s.substr(0,1);
                    }
    
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.