C++ Concise Solution


  • 18
    int findSubstringInWraproundString(string p) {
            vector<int> letters(26, 0);
            int res = 0, len = 0;
            for (int i = 0; i < p.size(); i++) {
                int cur = p[i] - 'a';
                if (i > 0 && p[i - 1] != (cur + 26 - 1) % 26 + 'a') len = 0;
                if (++len > letters[cur]) {
                    res += len - letters[cur];
                    letters[cur] = len;
                }
            }
            return res;
        }
    

  • 1

    @zyoppy008
    Concise and straightforward! Attached is the python version of your solution.
    Short explanation in case someone still confuse about zyoppy008's solution. Letters[i] represents the longest consecutive substring ended with chr(97+i), update res only when current L is bigger than letters[curr].

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            letters = [0] * 26
            res = L = curr = 0
            for i in range(len(p)):
                pre, curr = curr, ord(p[i]) - 97
                L = 1 if i > 0 and (pre + 1) % 26 != curr else L+1
                if L > letters[curr]:
                    res += L - letters[curr]
                    letters[curr] = L
            return res
    

  • 0
    H

    @zyoppy008 Briliant solution.


  • 5
    W

    more concise version:

    int findSubstringInWraproundString(string p) {
            vector<int> letters(26, 0);
            int len = 0;
            for (int i = 0; i < p.size(); i++) {
                int cur = p[i] - 'a';
                if (i > 0 && p[i - 1] != (cur + 26 - 1) % 26 + 'a') len = 0;
                letters[cur] = max(letters[cur], ++len);
            }
            return accumulate(letters.begin(), letters.end(), 0);
        }
    

  • 0
    G

    What an elegant solution!


Log in to reply
 

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