MiddleCodeOccasionalNot answered yet
Can a string become a palindrome by removing exactly one char?
Given a non-empty string, decide whether removing exactly one character can make it a palindrome. If the string is already a palindrome the answer is true (drop a central char). "aaab" → true, "xyz" → false.
Requirements:
- O(n) time, O(1) extra space.
bool canBePalindromeAfterOneRemoval(const std::string& s) {
// your code here
}Write the implementation.
Two pointers from both ends. On the first mismatch, try skipping either the left or the right character and check whether the remaining span is a palindrome. If the string is already a palindrome, removing a central char keeps it one, so return true. O(n), O(1).
- ✗Treating the spec as 'at most one' removal when it says exactly one
- ✗Checking only one side at the mismatch instead of trying both removals
- ✗Re-scanning the whole string for each candidate removal, making it O(n²)
- →How does 'exactly one' differ subtly from 'at most one' for an already-palindromic string?
- →Why is trying both sides at the first mismatch sufficient?
Contents
Task
Decide whether removing exactly one character can make the string a palindrome, in O(n).
Solution
static bool isPal(const std::string& s, int i, int j) {
while (i < j) { if (s[i++] != s[j--]) return false; }
return true;
}
bool canBePalindromeAfterOneRemoval(const std::string& s) {
int i = 0, j = s.size() - 1;
while (i < j) {
if (s[i] != s[j])
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
++i; --j;
}
return true; // already a palindrome -> drop a central char
}Key points
- Converge with pointers until the first mismatch.
- There, try skipping the left OR the right character.
- An already-palindrome also returns true (drop a central char).
Contents
