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;
}
}