LeetCode 467.

Question

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this:

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Given a string s, return the number of unique non-empty substrings of s are present in base.

Complexity

Time complexity: O(n^2)
Space complexity: O(n^2)

Code 1(TLE)

class Solution {
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        boolean[][] isqualified = new boolean[n][n];
        Set<String> uni = new HashSet<>();
        for (int i=0; i<n; i++) {
            isqualified[i][i] = true;
            if (!uni.contains(String.valueOf(s.charAt(i)))) {
                uni.add(String.valueOf(s.charAt(i)));
            }
        }

        for (int len=2; len<=n; len++) {
            for (int i=0; i<=n-len; i++) {
                String temp = s.substring(i, i + len);
                if (isqualified[i][i+len-2] && 
                    isconsecutive(s.charAt(i + len - 2), s.charAt(i + len - 1))) {
                    isqualified[i][i+len-1] = true;
                    uni.add(temp);
                }
            }
        }

        return uni.size();

    }

    public boolean isconsecutive(char former, char later) {
        if (later == 'a' && former == 'z') return true;
        else return later - former == 1;
    }
}

Complexity

Time complexity: O(n)
Space complexity: O(n)

Code 2

class Solution {
    public int findSubstringInWraproundString(String s) {
        int dp[] = new int[s.length()];
        dp[s.length() - 1] = 1;
        int maxArray[] = new int[26];
        maxArray[s.charAt(s.length()-1) - 'a'] = 1;
        for(int i = s.length() - 2 ; i >= 0 ; i--){
            if(s.charAt(i) == s.charAt(i+1) - 1 || s.charAt(i) == 'z' 
                && s.charAt(i+1) == 'a'){
                dp[i] = 1 + dp[i+1];
            }else{
                dp[i] = 1;
            }
            int key = s.charAt(i) - 'a';
            maxArray[key] = Math.max(maxArray[key],dp[i]);
        }
        int res = 0;
        for(int i=0;i<26;i++){
            res = res + maxArray[i];
        }
        return res;
    }
}

Check out the description of this problem at LC 467.