Ruby Solution


  • 0

    This answer is inspired by this post
    https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp

    The problem can be solved by bottom-up DP. For example, given input "abcxyz", we can first find the answer for string "a", then "ab", then "abc" and etc.

    In the following paragraph, substring refers to the substring presented in string s, unless otherwise mentioned.

    When we iterate though the string, we need to keep track of two things: (1) the length of the longest substring that ends at the current index position and (2) the # of substrings group by ending character

    index ↓          count
    input abcxyza    a b c x y z
          -          1 0 0 0 0 0
    
    index  ↓         count
    input abcxyza    a b c x y z
          --         1 2 0 0 0 0
    
    index   ↓        count
    input abcxyza    a b c x y z
          ---        1 2 3 0 0 0
    
    index    ↓       count
    input abcxyza    a b c x y z
             -       1 2 3 1 0 0
    
    index     ↓      count
    input abcxyza    a b c x y z
             --      1 2 3 1 2 0
    
    index      ↓     count
    input abcxyza    a b c x y z
             ---     1 2 3 1 2 3
    
    index       ↓    count
    input abcxyza    a b c x y z
             ----    4 2 3 1 2 3
    
    def find_substring_in_wrapround_string(p)
        len = 0
        counts = Hash.new(0)
        
        0.upto(p.size-1) do |index|
            char = p[index]
            if index > 0 && p[index-1] == prev(char)
                len += 1
            else
                len = 1
            end
            counts[char] = len if len > counts[char]
        end
        
        counts.inject(0) { |acc, (k,v)| acc+= v }
    end
    
    def prev(char)
        char == 'a' ? 'z' : (char.ord-1).chr
    end
    

Log in to reply
 

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