TopCoder problem "EqualSubstrings" used in SRM 221 (Division II Level One)

Problem Statement

You will be given a String str consisting of lowercase letters. You will return a String[] containing elements x and y in that order. The returned Strings x and y must satisfy:

1) The string xy (x with y concatenated on the end) must equal str.
2) The number of a's in x must equal the number of b's in y.
3) If multiple solutions are possible, use the one that maximizes the length of x.

See the examples for further clarifications.

Definition

Class:	EqualSubstrings
Method:	getSubstrings
Parameters:	String
Returns:	String[]
Method signature:	String[] getSubstrings(String str)
(be sure your method is public)

Constraints

str will contain between 1 and 50 characters inclusive.

Each character in str will be a lowercase letter ('a'-'z').

Examples

"aaabbb"

Returns: { "aaa",  "bbb" }

Here we can split str right down the center.

"bbbaaa"

Returns: { "bbb",  "aaa" }

Again the center works.

"bbbbbb"

Returns: { "bbbbbb",  "" }

y can be empty.

"aaaaaa"

Returns: { "",  "aaaaaa" }

x can be empty.

"abjlkbjalkbjaljsbljbalb"

Returns: { "abjlkbjalkbjaljs",  "bljbalb" }

Make sure to maximize the length of x.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3446

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5867&pm=3446

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

Brute Force