# Concise Java solution using DP

• After failed with pure math solution and time out with DFS solution, I finally realized that this is a DP problem...
The idea is, if we know the max number of unique substrings in `p` ends with `'a', 'b', ..., 'z'`, then the summary of them is the answer. Why is that?

1. The max number of unique substring ends with a letter equals to the length of max contiguous substring ends with that letter. Example `"abcd"`, the max number of unique substring ends with `'d'` is 4, apparently they are `"abcd", "bcd", "cd" and "d"`.
2. If there are overlapping, we only need to consider the longest one because it covers all the possible substrings. Example: `"abcdbcd"`, the max number of unique substring ends with `'d'` is 4 and all substrings formed by the 2nd `"bcd"` part are covered in the 4 substrings already.
3. No matter how long is a contiguous substring in `p`, it is in `s` since `s` has infinite length.
4. Now we know the max number of unique substrings in `p` ends with `'a', 'b', ..., 'z'` and those substrings are all in `s`. Summary is the answer, according to the question.

``````public class Solution {
public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26];

// store longest contiguous substring ends at current position.
int maxLengthCur = 0;

for (int i = 0; i < p.length(); i++) {
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25))) {
maxLengthCur++;
}
else {
maxLengthCur = 1;
}

int index = p.charAt(i) - 'a';
count[index] = Math.max(count[index], maxLengthCur);
}

// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
}
``````

• @shawngao Nice solution. However, you can get rid of the `dp` array like this:

``````public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26];
int maxLengthCur = 0;

for (int i = 0; i < p.length(); i++) {
int len = 1;
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25)))
maxLengthCur++;
else
maxLengthCur = 1;

int index = p.charAt(i) - 'a';
count[index] = Math.max(count[index], maxLengthCur);
}

// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
``````

• @dettier Thanks for you reply! Yes, you are right, we don't actually need an extra dp array since dp[i] is only rely on dp[i - 1]. This will improve space complexity to O(1). Will update my post.

• Good solution! I think the best part is counting for the length of the substring that ends with a character. I only thought of "starts with" which leads to O(N^2)... :P

• Thanks for your clever solution, and I am wondering why for"cac", ca, ac, cannot be treated as the substring, or the example of problem is wrong since it states that the input string is the
warpraound of abcdefghijklmnopqrstuvwxyzabcd.........

• I am wondering why for"cac", ca, ac, cannot be treated as the substring

Because "ca" and "ac" are not `substring` of `s`. The word `substring` indicates those are contiguous letters.

• Very good solution. Impressive !

• I wouldn't call this DP, why do you call it DP? More like a sliding window to me, if you choose to use starting letter instead of ending letter.

``````p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25

->

p.charAt(i) - 'a' == (p.charAt(i-1) - 'a' + 1) % 26
``````

• @iaming I second you.

• Great definition to define count[] as the length by ending letters. I had exactly the same solution but with count[] by starting letters, which is essentially the same but have to use an inner loop of max size 25 to update count[].

• Good solution! Easy to understand!

• Same boat ! I was stuck in using math knowledge at first and then move on to using map to cache the results of different combination result

OP's idea is like a WOW kind of solution, clean and elegant !

• @shawngao Maybe it is a dumb question, in the case of `cac`, why `ac` or `ca` are not a sub-string of `cac`?

• @shawngao Maybe it is a dumb question, in the case of `cac`, why `ac` or `ca` are not a sub-string of `cac`?

The substrings of `p = "cac"` to count need to be present in `s` by the definition of the problem. Note that the way `s` is constructed restricts that only substrings with chars in consecutive alphabetical order qualify (e.g., `"defg"`). So neither `"ac"` nor `"ca"` is present in `s` since char `'a'` and `'c'` are not consecutive in alphabet.

• @zzg_zzm That clarifies my confusion. Thanks~

• Elegant solution. Thanks.

• Golang version:

``````func findSubstringInWraproundString(p string) int {
count := make([]int, 26)
for k,_ := range count {
count[k] = 0
}
maxLengthCur := 0

for i:=0; i < len(p); i++ {
if i > 0 && (int(p[i]) - int(p[i-1]) == 1 || int(p[i-1]) - int(p[i]) == 25 ) {
maxLengthCur++
} else {
maxLengthCur = 1
}
index:= int(p[i]) - int('a')
count[index] = max(maxLengthCur, count[index])
}
sum := 0
for i:= 0; i < 26; i++ {
sum += count[i]
}
return sum
}

func max(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
``````

• Very nice @shawngao

• @shawngao
Thanks for the great solution.
The only thing I want to add is about the explanation. I found the term "the max number of unique substrings" was a bit confusing at the first glance. I think what you mean is "number of unique contiguous substrings/number of unique substrings with contiguous characters", is that correct?

• @AaronZhao I think I wanted to emphasize `max`. But your description also makes sense.

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