C++ O(n + 26*26) time O(1) solution


  • 0
    A

    We only need to find longest incrementing strings, which can be done in one-pass O(n).
    For such a string, if we delete its head char, it is still a valid incrementing string, but with a different head char and lenght-1.
    We can do this up to alphabet wraparound (26) or up to its length, whichever comes first.

    81 / 81 test cases passed
    Status: Accepted
    Runtime: 9 ms

    class Solution {
    public:
        int findSubstringInWraproundString(string p) {
            uint hash[26] = {0}, len = p.size(), sum = 0, b = 0;
            if (!len) return sum;
            for (uint i = 1; i <= len; i++) {
                if (i == len || p[i-1] == 'z' ? p[i] != 'a' : p[i] - p[i-1] != 1) {
                    uint c = p[b] - 'a', tmp = i - b;
                    if (tmp > hash[c]) hash[c] = tmp;
                    b = i;
                }
            }
            for (uint i = 0; i < 26; i++) {
                for (uint j = 1, jj = min(26u, hash[i]); j < jj; j++) {
                    int idx = (i + j) % 26, val = hash[i] - j;
                    if (val > hash[idx]) hash[idx] = val;
                }
            }
            for (uint i = 0; i < 26; i++) {
                sum += hash[i];
            }
            return sum;
        }
    };
    

Log in to reply
 

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