0 dynamic programming medium leetcode467. The only substring in the surrounding string

467. The unique substring in the surround string

analysis

Calculate with 26 The length of the longest substring ending with letters , Add up to the number of substrings that can be found in that infinite looping array .

All substrings are based on this 26 Letters ending . Find out respectively with 26 The longest substring ending with letters , You can get all the substrings .

Solution to the problem of the candle with a negative snow ：
The local idea is actually 「 The sliding window 」 and 「 Dynamic programming 」 Combination .
Dynamic programming of substring Correlation , The general definition of state is 「 By location ii Ending 、 The length of substring that meets the requirements 」.
Such definition , Mainly to simplify , Because I know dp[i]dp[i] in the future , It's easy to get dp[i + 1]dp[i+1].
For example, for this topic , We define the state as 「pp in , By location ii Ending 、 stay ss The longest substring length in 」.
So in the known dp[i]dp[i] in the future , obtain dp[i + 1]dp[i+1] when , There are only two situations ：

When in ss in , p[i + 1]p[i+1] yes p[i]p[i] The next character of , Then it means it can Connected to the , therefore dp[i + 1] = dp[i] + 1dp[i+1]=dp[i]+1.
When in ss in , p[i + 1]p[i+1] No p[i]p[i] The next character of , Then it means it can Can't connect , therefore dp[i + 1] = 1dp[i+1]=1.
author ：fuxuemingzhu
link ：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solution/by-fuxuemingzhu-ixas/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

class Solution {
    
    public int findSubstringInWraproundString(String p) {
    
char[] arr = p.toCharArray();
        int[] dp = new int[26];
        int len = 1;
        dp[arr[0]-'a'] = 1;
        for (int i = 1; i < arr.length; i++) {
    
            if (arr[i] - arr[i-1] == 1 || arr[i] == 'a' && arr[i-1] == 'z') {
    
                len++;
            } else {
    
                len = 1;
            }
            if (len > dp[arr[i]-'a']) {
    
                dp[arr[i]-'a'] = len;
            }
        }
        int ans = 0;
        for (int num : dp) {
    
            ans += num;
        }
        return ans;
    }
}