Java two different solutions with explanation


  • 3
    Z

    Hi there! I am sharing two different solutions with explanations.

    Well, the first solution idea is Optimized brute force. The 'naivest' way is for each substring of p in alphabetic order (with rotation %26) brute force all substrings and add to some set. Then at last just return size of the set. That method works but it has two problems, they are:

    • Memory limit
    • Time limit

    Because it works for O(n^3) time and O(n^2) space.
    How can we optimize memory? Because we are considering only strings in alphabetic order, it is sufficient to remember the first character index, last character index and the length for each found substring. This way we replace set of strings to 3D boolean array.
    Well, how can we optimize time complexity? We can increase performance of counting unique substrings for already found substring, which size is greater than 26. The evidence mentioned above helps us again, because we just need to consider combinations of first 26 character and the last 26 characters for different length, by incrementing length by 26. Such a way we get algorithm that runs for O(26*n) time and O((26^2)*n) space complexities.

    public class Solution {
        public int findSubstringInWraproundString(String p) {
            if(p == null || p.isEmpty()) return 0;
            boolean [][][] set = new boolean[26][26][p.length()+1];
            int i = 0;
            int count = 0;
            boolean [] visited = new boolean[26];
            StringBuilder build = new StringBuilder();
            char [] s = p.toCharArray();
            int n = s.length;
            while(i<n){
                char prev = s[i];
                build.append(prev);
                i++;
                while(i<p.length() && s[i]-'a' == (prev-'a'+1)%26){
                    prev = s[i];
                    build.append(prev);
                    i++;
                }
                
                String next = build.toString();
                int l = next.charAt(0)-'a';
                int r = next.charAt(next.length()-1)-'a';
                if(!set[l][r][next.length()]){
                    count++;
                    set[l][r][next.length()] = true;
                    count+= countUniqueSubstr(next, set);
                }
                build.setLength(0);
            }
            return count;
        }
        
       
        public int countUniqueSubstr(String str, boolean [][][] set){
            int count = 0;
            if(str.length()>26){
                int n = str.length();
                for(int i = 0;i<26;i++){
                    int l = str.charAt(i)-'a';
                    for(int j = n-1;j>=n-26;j--){
                        int r = str.charAt(j)-'a';
                        int limit = j-i+1;
                        int start = r-l+1;
                        if(r<l){
                            start = 27-l+r;
                        }
                        for(int size = start;size<=limit;size+=26){
                            if(!set[l][r][size]){
                                count++;
                                set[l][r][size] = true;
                            }
                        }
                    }
                }
                
            } else {
                for(int size = 1;size<str.length();size++){
                    for(int i = 0;i<=str.length()-size;i++){
                        String s = str.substring(i, i+size);
                        int l = s.charAt(0)-'a';
                        int r = s.charAt(s.length()-1)-'a';
                        if(!set[l][r][s.length()]){
                            count++;
                            set[l][r][s.length()] = true;
                        }
                    }
                }
            }
            return count;
        }
    }
    

    The second solution is simple, just keep track of maximum length of alphabetic substrings ending at certain character then sum them up.

    public class Solution {
        public int findSubstringInWraproundString(String p) {
            if(p == null || p.isEmpty()) return 0;
            int dp[] = new int[26];
            int i = 0;
            int n = p.length();
            char [] s = p.toCharArray();
            int len = 1;
            while(i<n){
                char prev = s[i];
                i++;
                dp[prev - 'a'] = Math.max(dp[prev-'a'], len);
                while(i<p.length() && s[i]-'a' == (prev-'a'+1)%26){
                    prev = s[i];
                    len++;
                    i++;
                    dp[prev - 'a'] = Math.max(dp[prev-'a'], len);
                }
                dp[prev - 'a'] = Math.max(dp[prev-'a'], len);
                len = 1;
            }
            int count = 0;
            for(int j = 0;j<26;j++) count+=dp[j];
            return count;
        }
    }
    

    P.S: Sorry for poor and dirty code. I hope it will be understandable anyway


Log in to reply
 

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