CODEWITHSUNDEEP
rubystring
ordinary
ordinary

Reputation: 6133

Finding if a string is a repeated substring in Ruby

Here is the problem: A string is called a k-string if it can be represented as k concatenated copies of some string. For example, the string "aabaabaabaab" is at the same time a 1-string, a 2-string and a 4-string, but it is not a 3-string, a 5-string, or a 6-string and so on. Obviously any string is a 1-string.

You are given a string s, consisting of lowercase English letters and a positive integer k. Your task is to reorder the letters in the string s in such a way that the resulting string is a k-string.

Input The first input line contains integer k (1 ≤ k ≤ 1000). The second line contains s, all characters in s are lowercase English letters. The string length s satisfies the inequality 1 ≤ |s| ≤ 1000, where |s| is the length of string s.

Output Rearrange the letters in string s in such a way that the result is a k-string. Print the result on a single output line. If there are multiple solutions, print any of them.

If the solution doesn't exist, print "-1" (without quotes).

Here is my code:

k = gets.to_i
str = gets.chomp.split(//)
n = str.length/k
map = Hash.new(0)
map2 = Hash.new(0)
str.each { |i| map[i] += 1 }

x = str.uniq.permutation(n).map(&:join).each do |string|
  string.each_char { |c| map2[c] += k }
  if map2 == map
    puts string*k
    exit
  end
  map2 = Hash.new(0)
end

puts '-1'

To me this solution seems like it should work, but it fails on a test case. Can anyone tell me why?

Upvotes: 0

Views: 905

Answers (1)

000
000

Reputation: 27247

Here's my solution.

Just create one segment, then output it k times. If a character does not appear k times (or a multiple of it), then stop early and output -1.

k = gets.to_i
str = gets.chomp.split(//)
counts = Hash.new(0)
str.each { |i| counts[i] += 1 }

out = ''
str.uniq.each do |c|
  if counts[c] % k != 0
    puts -1
    exit
  end
  out = out + c*(counts[c]/k)
end

puts out*k

Upvotes: 1

Related Questions