Problem Statement |
| | John and Brus are going to open a boring store.
They would like to have a really boring name for it.
John has one wooden plate with an old store name on it.
Brus also has one.
Now they need to compose two plates with the same name (case-sensitive) for the new store.
They would like to produce these new plates as follows:
- John will cut two pieces from his plate. Each of the pieces will contain a non-empty contiguous substring of the name written on the original plate and the locations of these two substrings within the plate will not overlap. For example, if the name on John's plate is "abCDeF", then he can cut pieces with "bC" and "e" or with "CDeF" and "ab", but he can't cut pieces with "aC" and "eF" ("aC" is not a contiguous substring), with "abCD" and "" (empty substring is not allowed) or with "DeF" and "CD" (locations of the substrings overlap). Let's denote the substrings on John's pieces as A and B.
- Brus will cut two pieces from his plate according to the same rules. Let's denote the substrings on these pieces as C and D.
- One plate for the new store will be constructed as A + C (where '+' means concatenation of two strings) and another plate will be constructed as B + D.
You are given two Strings J and B - the names on John's and Brus's plates respectively.
Return the longest possible name for the new store that can be achieved as described above.
In case of a tie choose the one that comes first lexicographically.
If it is impossible to achieve the goal, return an empty String.
|
| |
Definition |
| | | Class: | TheBoringStoreDivTwo | | Method: | find | | Parameters: | String, String | | Returns: | String | | Method signature: | String find(String J, String B) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | If two Strings A and B have the same length, then A comes before B lexicographically if it has a smaller character at the first position where the Strings differ. When comparing the characters, refer to the following list of characters in ascending order: 'A', 'B', ..., 'Z', 'a', 'b', ..., 'z'. |
| |
Constraints |
| - | J will contain between 1 and 15 characters, inclusive. |
| - | B will contain between 1 and 15 characters, inclusive. |
| - | Each character of J will be an uppercase or lowercase letter ('a' - 'z', 'A' - 'Z'). |
| - | Each character of B will be an uppercase or lowercase letter ('a' - 'z', 'A' - 'Z'). |
| |
Examples |
| 0) | |
| | "StoreOfJohn" | "StoreOfBrus" |
| Returns: "or" | | John's plate contains two 'o's, and Brus's plate contains two 'r's, so one possible solution is for each new plate to contain one 'o' from John's plate and one 'r' from Brus's plate. |
|
|
| 1) | |
| | | Returns: "" | | The name on both new plates must end with a character from one of Brus's pieces. However, all characters on Brus's plate are different, so it is impossible to achieve the goal. |
|
|
| 2) | |
| | "JohnPlaysGames" | "BrusAlsoPlays" |
| Returns: "ays" | |
|
| 3) | |
| | "abacaba" | "abacabadabacaba" |
| Returns: "abaabacaba" | |
|