C++ 9 lines O(n) method


  • 7
    W
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int m[256];
            fill(m, m+256, -1);
            int maxLen = 0, lastRepeatPos = -1;
            for(int i=0; i<s.size(); i++) {
                if (m[s[i]]!=-1 && lastRepeatPos < m[s[i]]) lastRepeatPos = m[s[i]];
                if ( i - lastRepeatPos > maxLen ) maxLen = i - lastRepeatPos;
                m[s[i]] = i;
            }
            return maxLen;
        }
    };

  • 1
    class Solution {
    public:
        int lengthOfLongestSubstring(std::string s) {
            std::vector<int> flag(256, -1);
            int start = 0, res = 0, len = s.size();
            for (int i = 0; i != len; ++i) {
                if (flag[s[i]] >= start) {
                    res = std::max(res, i - start);
                    start = flag[s[i]] + 1;
                }
                flag[s[i]] = i;
            }
            return std::max(res, len - start);
        }
    };

  • 0

    Could you explan it to me? Thank you!!


  • 0
    Z

    code without explanation is insignificant!!!!!!!!!!!


  • 0

    same as the top voted answer...


Log in to reply
 

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