SquareFreeString

SRM 701 · 2016-10-02 · by Arterm

SRM 701 · 2016-10-02 · by Arterm · String Manipulation

Show categories

Class Name: SquareFreeString

Return Type: String

Method Name: isSquareFree

Arg Types: (string)

Problem Statement

We say that a string S is a square if it has the form TT, where T is some non-empty string. In other words, a square is a string that is a concatenation of two copies of the same non-empty string. For example, the strings "aa", "bbbb", and "beriberi" are squares.

A string is called square-free if none of its substrings is a square. For example, the string "abca" is square-free. (The substrings of this string are the strings "a", "b", "c", "a", "ab", "bc", "ca", "abc", "bca", and "abca". None of these strings is a square.)

You are given a String s. Return "square-free" if s is square-free. Otherwise, return "not square-free". Note that the return value is case-sensitive.

Constraints

s will consist only of lowercase English letters ('a'-'z').
The length of s will be between 1 and 50, inclusive.

Examples

"w"
Returns: "square-free"

"cb"
Returns: "square-free"

"qok"
Returns: "square-free"

"aegi"
Returns: "square-free"

"oqquy"
Returns: "not square-free"

29)

"bobo"
Returns: "not square-free"

"bobo" = T + T, where T = "bo", so it is not square-free.

30)

"apple"
Returns: "not square-free"

Substring "pp" is a square.

31)

"pen"
Returns: "square-free"

"pen" does not contain any substrings that are squares.

Submissions are judged against all 56 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SquareFreeString with a public method string isSquareFree(string s) · 56 test cases · 2 s / 256 MB per case