467. Unique Substrings in Wraparound String

Link

Solution

首先要觀察到一個特質， p中的子字串的結尾必定是a-z中的一個字元

而子字串以某一個某字元結尾的最大合法字串的長度，即是以這個字元結尾的合法組合數

ex. 假設abcd是字串p中以d結尾的最大子字串，那麼它能帶來的以d結尾的組合有 d, cd, bcd, abcd，剛好數目就是字串長度。

所以我們只需要把26個字元結尾的最大合法子字串的長度都進行累加，就可以得到答案。

  public int findSubstringInWraproundString(String p) {
        int[] nums = new int[26];
        int maxLen = 0;
        char preChar = 0;
        for(int i = 0; i < p.length(); i++){
            char curChar = p.charAt(i);
            if(i > 0 && curChar == preChar+1 || preChar == 'z' && curChar == 'a'){
                maxLen++;
            }
            else{
                maxLen = 1;
            }
            nums[curChar-'a'] = Math.max(maxLen, nums[curChar-'a']);
            preChar = curChar;
        }
        int ans = 0;
        for(int num : nums){
            ans += num;
        }
        return ans;
    }