Accepted 16ms c++ DP solution, O(n), with bitmask to record the last position of each letter appears


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

    Updated Jun 30: In fact, there is no need to update longest evey time:

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

  • 0
    2

    I have a question,
    why you think this solution is DP?

    I think this question's key is how to choose Start when find a repeat char.

    Could you tell me your DP thinking?

    Thanks you!


  • 0

    In my understanding, the dynamic programming is: every decision depends on the current status, and immediately cause the transfer of status. In this problem, flag is the status, and we can get the longest every time depends on the previous longest and the flag, so I think it also can be seen as DP solution, even though not obvious compared to the Maximum Subarray problem.


  • 0
    2

    I've got it.
    Thank you~!


Log in to reply
 

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