Cassidoo’s Interview question of the week | 453

Learning Resources
1

Hello :waving_hand:

This week question is about finding the maximum number of non-overlapping copies in given string.

Given a string s containing letters and ? wildcards (that can match any letter), and a target pattern string pattern, rearrange the entire string however you like. Return the maximum number of non-overlapping copies of pattern that can appear in the rearranged result.

maxPatternCopies("abcabc???", "ac")  // 3

maxPatternCopies("aab??", "aab")  // 1

maxPatternCopies("??????", "abc")  // 2

Happy coding!

2 Likes
2

This one was tougher than I thought it would be!

Solution 
def max_pattern_copies(string, pattern)
  wildcards = string.count("?")
  string_char_counts = string.chars.tally.except("?")
  pattern_char_counts = pattern.chars.tally
  max_matches = string.length / pattern.length

  (0..max_matches).reverse_each.find do |candidate_match_count|
    wildcards_needed = pattern_char_counts.sum { |pattern_char, pattern_char_count|
      actual_occurrences_in_string = string_char_counts[pattern_char] || 0
      needed_occurrences_for_match_count = candidate_match_count * pattern_char_count
      [0, needed_occurrences_for_match_count - actual_occurrences_in_string].max
    }
    wildcards_needed <= wildcards
  end
end
3

To honest, I tried and failed. I gave up. It was hard :sweat_smile:

4

There have been some past weeks recently that I didn’t even try because they seemed difficult and I knew I’d have to spend too much time on them. This week I was baited by the seeming simplicity of the problem :smiling_face_with_tear:

5

Same here, they look “simple”… I usually give it a try to solve them after work, but my human brain is depleted of “tokens” :smiling_face_with_tear:

6
Thanks, Hi 

def count(str, pattern)
  map = str.split("").reduce({}) do |memo, char|
    memo[char] ||= 0
    memo[char] += 1
    memo
  end

  i = 0
  count = 0

  loop do
    if i >= pattern.size
      count += 1
      i = 0
    end

    char = pattern[i]

    if map[char]&.>(0)
      map[char] -= 1
    elsif map["?"]&.>(0)
      map["?"] -= 1
    else
      break 
    end

    i += 1
  end

  count
end


puts count("abcabc???", "ac") # 3
puts count("aab??", "aab")  # 1
puts count("??????", "abc") # 2
3 Likes
7

Nice, I love that solution :heart:

1 Like
8
solution 
def maxPatternCopies string, pattern
  chars = string.chars
  (0..).find do
    pattern.each_char.find do |char|
      index = chars.index(char) || chars.index("?")
      if index then 
        chars[index] = nil
      else
        true
      end
    end
  end
end