Determine if a String has a mirroring head and tail

Question

Problem statement:

Given a string, look for a mirror image (backwards) string at both the beginning and end of the given string. In other words, zero or more characters at the very begining of the given string, and at the very end of the string in reverse order (possibly overlapping). For example, the string "abXYZba" has the mirror end "ab".

Examples:

• mirrorEnds("abXYZba") → "ab"
• mirrorEnds("abca") → "a"
• mirrorEnds("aba") → "aba"

Below is my solution to the problem in java:

public String mirrorEnds(String string) {
 final int len = string.length();
 final int half = len / 2;
 String result = "";
 for (int i = 0; i < half; i++) {
 if (string.charAt(i) != string.charAt(len -1 -i)) {
 break; 
 } else {
 result += string.substring(i, i + 1);
 }
 }
 return result.length() == half ? string : result;
}

Is it safe to say that in terms of time complexity the solution is optimal already? Any other review comments are also welcome.

• Eric Towers: I observe that the problem statement does not specify anything about the output and the title indicates that the output is a boolean, not a string.
• Richard Donovan: Reverse the string into string1 then compare String to String1 for length = 1 to StringLength / 2?

Answer 1

I don't program much in Java, but suspect it is suboptimal to be building the string in the loop one character at a time.

Also, calculating a "fresh" tail end position each time from base units may take cycles, rather than decrementing a reverse counter. You then end up with an empty else{}, which should also help loop optimisation.

So something like, where j (as a variable that survives loop destruction) is overloaded to be the "tail test" position in the loop, and the number of matched characters as the loop exits: [BTW, can't test this as no Java system to hand - just editing as I go. Particularly check the final arithmetic on "j".]

 public String mirrorEnds(String string) {
 final int len = string.length();
 final int half = len / 2;
 int j = len - 1;
 for (int i = 0; i < half; i++) {
 if (string.charAt(i) != string.charAt(j--)) {
 j = len - j - 1; 
 break; 
 }
 }
 return j == half ? string : string.substring(0, j);
 }

or

public String mirrorEnds(String string) {
 int len = string.length();
 final int half = len / 2;
 int i = 0; 
 while (i < half) {
 if (string.charAt(i) != string.charAt(--len)) {
 break; 
 }
 i++;
 }
 return i == half ? string : string.substring(0, i);
 }

Answer 2

Below your question:

Is it safe to say that in terms of time complexity the solution is optimal already?

Yes, you are comparing chars from front and back of the string and stop when you encounter two different chars so this is a complexity O(n).

Some minor changes to your code, instead of iterate over your string transform it to a char array and instead of break the cycle return directly the result with the use of a StringBuilder for the result:

char[] arr = string.toCharArray();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < half; ++i) {
 if (arr[i] != arr[len -1 -i]) {
 return builder.toString();
 }
 builder.append(arr[i]);
}
return string;

In this way you avoid the use of consecutive creation of substrings and the code is simpler.

Your method can be rewritten then in this equivalent way:

public static String mirrorEnds(String string) {
 final int len = string.length();
 final int half = len / 2;
 char[] arr = string.toCharArray();
 StringBuilder builder = new StringBuilder();
 for (int i = 0; i < half; ++i) {
 if (arr[i] != arr[len -1 -i]) {
 return builder.toString();
 }
 builder.append(arr[i]);
 }
 return string;
}

• hc_dev: Could also use int mirroredPosition = string.length()-1 decreasing inside loop instead of len-1 -i to make it clear. Optionally check for null or empty string before.
• dariosicily: @hc_dev. Agree ,it is possible to use mirroredPosition. If the string is null it will raise the NPE when you call length() and in case of empty string it will not enter the cycle directly returning the empty string.
• Turksarama: You don't even need StringBuilder. If you just take a substring of the original string with the right number of elements, you're done.
• Konrad Rudolph: The repeated string concatenation means that OP's code does not have optimal time complexity, contrary to what you've said. It has worst case O(n^2) instead of linear runtime.
• Konrad Rudolph: @dariosicily The substring operation is constant (though needlessly inefficient). The string concatenation is not constant, since each concatenation operation will reallocate a larger buffer and copy all existing elements over (so each string concatenation is an O(n) operation in the length of the string, which in OP’s case goes from 1–n/2, and the sum of that is bounded by O(n^2)). This is fixed by your use of the StringBuilder, which has an (amortised) constant-time append operation.

Answer 3

Algorithmic shortcuts like this should be documented with comments.

// Reaching half point means the string is a palindrome
return result.length() == half ? string : result;

Dariosicily had everything else covered.

• hc_dev: Agree on that advice, would even put that palindrome comment above for or at breaking inside, since explaining the loop's exit-condition.
• hc_dev: Sorry Torben! Thought I was in plain SO first, then commented & downvoted. Think you must edit before I can revoke/upvote again 😲

Answer 4

The pattern of mirrored string is used also by algorithms that ckeck for a Palindrome .

Such a Palindrome & Java question was Check string for palindrome

Inspired by Palindrome checker

Inspired by one of the answers which was both concise and elegant:

public static boolean isPalindrome(String s) {
 for (int i=0 , j=s.length()-1 ; i<j ; i++ , j-- ) {
 if ( s.charAt(i) != s.charAt(j) ) {
 return false;
 }
 } 
 return true;
}

I adjusted exit-condition from i<j to i < half (comparing dynamic parts not needed).

Then your extracting function may be implemented like this:

public static String findMirroredPart(String s) {
 // optionally: check for null or empty respectively blank text
 final int half = s.length / 2;
 int i=0;
 for (int j = s.length()-1; i < half ; i++, j-- ) {
 if (s.charAt(i) != s.charAt(j)) {
 break;
 }
 }
 String mirroredPartOrPalindrome = i < half ? s.substring(0,i) : s;
 return mirroredPartOrPalindrome;
}

Benefits are:

• name expresses what's happening: findMirroredPart (also static)
• mirrored position j is decreased inside for-definition (cleaner loop body; faster than calculating it using deepness i inside loop)
• result & ternary expression explained by variable
• result string building is done outside loop, once only (better performance)

More expressive: replace loop for by while

Since above for-loop's body only responsible to check and exit this votes for replace it by while. Body then would express its purpose: increase mirroring position thus final lenght of mirroredPart.

public static String findMirroredPart(String s) {
 // optionally: check for null or empty respectively blank text
 final int half = s.length / 2;
 int posFromBegin = 0;
 int posFromEnd = s.length() - 1;
 while (posFromBegin < half && s.charAt(posFromBegin) == s.charAt(posFromEnd)) {
 posFromBegin++;
 posFromEnd--;
 }
 String mirroredPartOrPalindrome = posFromBegin < half ? s.substring(0, posFromBegin) : s;
 return mirroredPartOrPalindrome;
}

Note: Introduced more expressive index names.