O(n) time. O(alphabet size) memory. Store maximum length for each alphabet


  • 1
    A
    1. O(n) time complexity. O(alphabet size) memory space. We can do it by calculating the maximum length of sequential characters for each alphabet. At the end we can just sum up the all maximum lengths of each alphabet.
    public class Solution {
        public int findSubstringInWraproundString(String p) {
            if (p==null || p.isEmpty()) return 0;
           
            HashMap<Character, Integer> charMaxLen = new HashMap<>();
            charMaxLen.put(p.charAt(0), 1);
            int sum = 1;
            int len = 1;
            
            for (int i=1; i<p.length(); i++) {
                char prev = p.charAt(i-1);
                char cur = p.charAt(i);
                if (isSequential(prev, cur)) {
                    len++;
                } else {
                    len = 1;
                }
                
                sum+=Math.max(len-charMaxLen.getOrDefault(cur,0), 0);
                charMaxLen.putIfAbsent(cur, 0);
                charMaxLen.put(cur, Math.max(len, charMaxLen.get(cur)));
            }
            return sum;
        }
        
        private boolean isSequential(char prev, char cur) {
            return (prev=='z' && cur=='a') || (cur-prev==1);
        }
    }
    

  • 0
    P

    Nice solution! I like it!


Log in to reply
 

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