# Convert a string to a palindrome

• Given a string S, whether we can convert it to a palindrome by adding a character inside the string.

For example:

Given "ab", return true.

Given "abcd", return false.

• Maybe there's a better way to solve this problem, I just want to share my solution here. The idea is straightforward, check from both ends of the input string till we find a mismatch at `s[i]` and `s[j]`, then try to append `s[i]` to `s[i...j]` and see if it forms a palindrome, if not, try to prepend `s[j]` to `s[i...j]` and see if it works. Time complexity is `O(n)`.

``````public class Solution {

public boolean canConvert(String s) {
int i = 0, j = s.length() - 1;

while (i < j && s.charAt(i) == s.charAt(j)) {
i++; j--;
}

return i >= j ||
isPalindrome(s.charAt(j) + s.substring(i, j + 1)) ||
isPalindrome(s.substring(i, j + 1) + s.charAt(i));
}

boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;

while (i < j && s.charAt(i) == s.charAt(j)) {
i++; j--;
}

return i >= j;
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.