-1

leetcode 680 https://leetcode.com/problems/valid-palindrome-ii/ asks to find a palindrome after deleting at most one character from it. I wrote the following code, but it turns out to fail for string "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga" because the r value becomes 80 in the ends program entering the outer else case in which the functions return false. The program has passed the most tests so I'm not sure what's the problem of this program.

public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        boolean deleted = false;
        while (l < r) {
            System.out.println(s.charAt(l));
            if (s.charAt(l) == s.charAt(r)) {
                l++;
                r--;

            } else if (!deleted) {
                deleted = true;
                if (s.charAt(l + 1) == s.charAt(r)) {
                    l++;
                } else if (s.charAt(l) == s.charAt(r - 1)) {
                    r--;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
iw2fs
  • 19
  • 1
  • 1
    When you check for the possible character to delete, don't just check l+1 and r or l and r-1 also check l+2 and r-1 or l+1 and r-1. – Martheen Dec 26 '21 at 05:41
  • Here's a little logging function. Print that out each row and it might help you see the problem. `static void log(String s, int l, int r) { System.out.println(s.substring(0, l) + "(" + s.charAt(l) + ")" + s.substring(l+1, r) + "[" + s.charAt(r) + "]" + s.substring(r+1)); }` – tgdavies Dec 26 '21 at 05:44

1 Answers1

1

This test fails because you assume that only one of the two conditions in

     if (s.charAt(l + 1) == s.charAt(r)) {
           l++;
      } else if (s.charAt(l) == s.charAt(r - 1)) {
           r--;

Is true. In the given test case when l=19 and r=81 both are true so you need to decide which one to apply.
To demonstrate the issue change the order of the two conditions:

        if (s.charAt(l) == s.charAt(r-1)) {
            r--;
        } else if (s.charAt(l+1) == s.charAt(r)) {
            l++;

The change does not fix the issue, just demonstrate it.

(You may find this helpful: What is a debugger and how can it help me diagnose problems?)

c0der
  • 18,467
  • 6
  • 33
  • 65