SRM 698 DIV2 Medium(500) - RepeatStringEasy

Problem Statement

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 erasing some (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.

Definition

  • Class: RepeatStringEasy
  • Method: maximalLength
  • Parameters: String
  • Returns: int
  • Method signature: int maximalLength(String s) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 256

Constraints

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

Solution Plan

与えられた文字列をs1とs2の2つの文字列に分解し、LCS(Longest Common Subsequence)を抽出する。 example1を例にすると、分解した文字列とLCSは以下のようになる。

  • S1:f S2:rankfurt LCS:f
  • S1:fr S2:ankfurt LCS:fr
  • S1:fra S2:nkfurt LCS:fr
  • S1:fran S2:kfurt LCS:fr
  • S1:frank S2:furt LCS:r
  • S1:frankf S2:urt LCS:r
  • S1:frankfu S2:rt LCS:r
  • S1:frankfur S2:t LCS:(none)

LCSの求め方

S1のi番目とS2のj番目までを比較したLCS長をLCS(i, j)とすると、以下の3つがわかれば求めることができる。

  • LCS(i-1, j-1)
  • LCS(i, j-1)
  • LCS(i-1, j)

その理由を文字列の最後の文字が一致しているかどうかで場合分けして考えてみる。

最後の文字が一致しているパターン

このパターンでは、LCS(i, j) = LCS(i-1, j-1) + 1となる。
具体例で示すと、
S1:AABBDC
S2:ADDBBC
の場合、AABBDCとADDBBCのLCSはAABBDとADDBBのLCS + 1となる。
最後の文字が一致しているため、その1つ前までのLCSに+1すればOK。

最後の文字が一致していないパターン

このパターンでは、LCS(i, j) = Max(LCS(i, j-1), LCS(i-1, j)となる。
こちらも具体例を示すと、
S1:AABBD
S2:ADDBB
の場合は、AABB, ADDBBのLCS(=ABB)とAABBD, ADDBのLCS(=AB)の大きい方をLCS(i, j)とする。

Source Code

public class RepeatStringEasy {

    public int maximalLength(String s) {
        if (s.length() == 1) return 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            max = Math.max(max, lcs(s.substring(0, i + 1), s.substring(i + 1, s.length())));
        }
        return max * 2;
    }

    private int lcs(String x, String y) {
        int[][] dp = new int[x.length() + 1][y.length() + 1];
        int max = 0;
        for (int i = 1; i <= x.length(); i++) {
            for (int j = 1; j <= y.length(); j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}