Concise Java solution using DP


  • 125

    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.

    Hope I made myself clear...

    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;
        }
    }
    

  • 3

    @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;
    }
    

  • 0

    @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.


  • 5
    M

    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


  • 0
    Z

    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.........


  • 3

    @zjukaili said in Concise Java solution using DP:

    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.


  • 0
    V

    Very good solution. Impressive !


  • 3
    I

    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
    

  • 0
    M

    @iaming I second you.


  • 0

    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[].


  • 0
    K

    Good solution! Easy to understand!


  • 0
    M

    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 !


  • 0
    D

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


  • 0

    @dukeforever said in Concise Java solution using DP:

    @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.


  • 0
    D

    @zzg_zzm That clarifies my confusion. Thanks~


  • 0

    Elegant solution. Thanks.


  • 0
    R

    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
        }
    }
    

  • 0
    J

    Very nice @shawngao


  • 0
    A

    @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?


  • 0

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


Log in to reply
 

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