I don't think the main idea for this problem is DP

  • 0

    I've seen many people's posts. They use the vector<int>(26,0) to store the max length of substring in Wraparound String that ended by a fixed char. And the result is simply sum of the vector.

    This method mainly apply the property that: the length of the longest valid substring ended by some char is the total number of unique substring in Wraparound String that ended by that char.

    For example, if vec[0] = 4, which means the longest substring in Wraparound String, tailed by 'a', is 'xyza'. Then, any valid substring tailed by 'a' can only be chosen from these 4 candidates:
    'xyza', 'yza', 'za', and 'a' , since we need unique.

    But the tags and someone's titles really confused me, and I spend several hours working on normal dp solutions, which of course got TLE.

Log in to reply

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