SquareFreeString | Topcoder Archive

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.

Definition

Class:: SquareFreeString
Method:: isSquareFree
Parameters:: String
Returns:: String
Method signature:: String isSquareFree(String s)
(be sure your method is public)

Constraints

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

Examples

```
"bobo"
```
```
Returns: "not square-free"
```
"bobo" = T + T, where T = "bo", so it is not square-free.
```
"apple"
```
```
Returns: "not square-free"
```
Substring "pp" is a square.
```
"pen"
```
```
Returns: "square-free"
```
"pen" does not contain any substrings that are squares.

"aydyamrbnauhftmphyrooyq"

Returns: "not square-free"

"qwertyuiopasdfghjklzxcvbnm"

Returns: "square-free"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.