Force deduction solution summary 467- unique substring in surrounding string

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ：

Power button

describe ：

Put the string s See as  “abcdefghijklmnopqrstuvwxyz”  Infinite wrapping string of , therefore  s It looks like this ：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
Now give another string p . return  s in   only Of p Of Non empty substring   The number of  . 

Example  1:

Input : p = "a"
Output : 1
explain : character string s Only one of them "a" Sub character .
Example 2:

Input : p = "cac"
Output : 2
explain : character string s String in “cac” Only two substrings “a”、“c”..
Example 3:

Input : p = "zab"
Output : 6
explain : In string s There are six substrings in “z”、“a”、“b”、“za”、“ab”、“zab”.
 

Tips :

1 <= p.length <= 105
p  Composed of lowercase English letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/unique-substrings-in-wraparound-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  The core is to find the string beginning with a certain letter , What is the longest length . The short one must be a long substring .

Code ：

public class Solution467 {

    public int findSubstringInWraproundString(String p) {
        int[] dp = new int[26];
        int k = 0;
        for (int i = 0; i < p.length(); ++i) {
            if (i > 0 && (p.charAt(i) - p.charAt(i - 1) + 26) % 26 == 1) { //  The difference between characters is  1  or  -25
                ++k;
            } else {
                k = 1;
            }
            dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], k);
        }
        return Arrays.stream(dp).sum();
    }
}