Java sliding window solutions


  • 0
    J

    The first solution is a sliding window solution. The second is more like dp, which is the same as in other posts, while I think its an optimization upon the first one.

        // O(N) two pointer counting number of substrings starting at char c
        public int findSubstringInWraproundString(String p) {
            if (p.isEmpty()) return 0;
            char[] chars = p.toCharArray();
            int[] dp = new int[26];
            int j = 0;
            for (int i = 0; i < chars.length; i++) {
                char cur = chars[i];
                if ((i + 1) == chars.length || (cur + 1) != chars[i + 1] && (cur != 'z' || chars[i + 1] != 'a')) {
                    while (j < i + 1) {
                        int ind = chars[j] - 'a';
                        dp[ind] = Math.max(dp[ind], i - j + 1);
                        j++;
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < 26; i++) res += dp[i];
            return res;
        }
    
    // O(N) one pointer counting number of substrings ending at char c
        public int findSubstringInWraproundString(String p) {
            if (p.isEmpty()) return 0;
            char[] chars = p.toCharArray();
            int[] dp = new int[26];
            int maxLen = 0;
            for (int i = 0; i < chars.length; i++) {
                char cur = chars[i];
                if (i == 0 || (cur - 1) != chars[i - 1] && (cur != 'a' || chars[i - 1] != 'z')) {
                    maxLen = 0;
                }
                dp[cur - 'a'] = Math.max(dp[cur - 'a'], ++maxLen);
            }
            int res = 0;
            for (int i = 0; i < 26; i++) res += dp[i];
            return res;
        }
    
    

Log in to reply
 

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