AtCoder BC097 C: K-th Substring - 銀の弾丸を探して

最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点？って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列挙してしまえば良いことに気づきました。

計算量としては、Kが5だったとしても、長さ1、2、3、4、5の部分文字列を求めるだけであり、各部分文字列を求める計算量はO(N)なので、十分間に合います。

s = gets.chomp.split("")
k = gets.chomp.to_i

a = []
1.upto(k) do |i|
  s.each_cons(i) {|ary| a << ary.join}
end

puts a.sort.uniq[k-1]