square_string.rb

#!usr/bin/ruby

# A string S is called a square if there is some string T such that S = T + T. For example, the strings "", aabaab" and "xxxx" are squares, but "a", "aabb" and "aabbaa" are not.

# You are given a String s. Find the longest square string that can be obtained from s by erasingsome (possibly none, possibly all) of its characters. In other words, we are looking for the longest square that occurs in s as a subsequence. Return the length of that square.

# Note that the answer is well-defined, as the square "" (the empty string) will always occur in s as a subsequence.

# Input Format

# An alphabetic string

# Constraints

# s will contain between 1 and 50 characters, inclusive.
# Each character in s will be a lowercase English letter ('a'-'z')
# Output Format

# You should print the lenght of the longest square that occurs in s as a subsequence

# Example 1:
# Input: "frankfurt"
# Expected output: 4
# The longest square that occurs in "frankfurt" is "frfr". Its length is 4.

# Example 2:
# Input: "single"
# Expected output: 0
# The letters in the string "single" are all distinct. Hence, the only square that occurs in this string is "". The length of this square is zero.

# Sample Input 0

# frankfurt
# Sample Output 0

# 4
# Sample Input 1

# single
# Sample Output 1

# 0
# Sample Input 2

# singing
# Sample Output 2

# 6
# Sample Input 3

# aababbababbabbbbabbabb
# Sample Output 3

# 18
# Sample Input 4

# x
# Sample Output 4

# 0

class SquareString
  attr_accessor :input

  def initialize
    @input = gets.chop
  end

  def largest
    max = 0
    for i in 0..input.size-2 do
      size = size_of_longest_common_subsequence(@input[0..i], @input[i+1, @input.size-1])
      max = size if size > max
    end
    return max*2
  end

  private

  def size_of_longest_common_subsequence(str_1, str_2)
    dp = Array.new(str_1.length+1) { Array.new(str_2.length+1, 0) }

    for i in 1..str_1.length do
      for j in 1..str_2.length do
        if (str_1[i-1] == str_2[j-1])
          dp[i][j] =  1 + dp[i-1][j-1]
        else
          dp[i][j] = [dp[i][j-1], dp[i-1][j]].max
        end
      end
    end
    return dp[str_1.length][str_2.length];
  end
end

s = SquareString.new
puts s.largest