Valid Palindrome II

Medium Strings

Return true if the string can become a palindrome after deleting at most one character. Two pointers with a single-skip check.

Sample input

abca

Sample output

true

Solution

def valid_palindrome(s):
    def is_pal(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return is_pal(lo + 1, hi) or is_pal(lo, hi - 1)
        lo += 1
        hi -= 1
    return True

print(valid_palindrome("abca"))

function validPalindrome(s) {
  const isPal = (lo, hi) => {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++;
      hi--;
    }
    return true;
  };
  let lo = 0, hi = s.length - 1;
  while (lo < hi) {
    if (s[lo] !== s[hi]) {
      return isPal(lo + 1, hi) || isPal(lo, hi - 1);
    }
    lo++;
    hi--;
  }
  return true;
}

console.log(validPalindrome("abca"));

public class Main {
    static boolean isPal(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo) != s.charAt(hi)) return false;
            lo++;
            hi--;
        }
        return true;
    }

    static boolean validPalindrome(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            if (s.charAt(lo) != s.charAt(hi)) {
                return isPal(s, lo + 1, hi) || isPal(s, lo, hi - 1);
            }
            lo++;
            hi--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(validPalindrome("abca"));
    }
}

fun isPal(s: String, start: Int, end: Int): Boolean {
    var lo = start
    var hi = end
    while (lo < hi) {
        if (s[lo] != s[hi]) return false
        lo++
        hi--
    }
    return true
}

fun validPalindrome(s: String): Boolean {
    var lo = 0
    var hi = s.length - 1
    while (lo < hi) {
        if (s[lo] != s[hi]) {
            return isPal(s, lo + 1, hi) || isPal(s, lo, hi - 1)
        }
        lo++
        hi--
    }
    return true
}

fun main() {
    println(validPalindrome("abca"))
}

func isPal(_ chars: [Character], _ start: Int, _ end: Int) -> Bool {
    var lo = start, hi = end
    while lo < hi {
        if chars[lo] != chars[hi] { return false }
        lo += 1
        hi -= 1
    }
    return true
}

func validPalindrome(_ s: String) -> Bool {
    let chars = Array(s)
    var lo = 0, hi = chars.count - 1
    while lo < hi {
        if chars[lo] != chars[hi] {
            return isPal(chars, lo + 1, hi) || isPal(chars, lo, hi - 1)
        }
        lo += 1
        hi -= 1
    }
    return true
}

print(validPalindrome("abca"))

bool isPal(String s, int lo, int hi) {
  while (lo < hi) {
    if (s[lo] != s[hi]) return false;
    lo++;
    hi--;
  }
  return true;
}

bool validPalindrome(String s) {
  int lo = 0, hi = s.length - 1;
  while (lo < hi) {
    if (s[lo] != s[hi]) {
      return isPal(s, lo + 1, hi) || isPal(s, lo, hi - 1);
    }
    lo++;
    hi--;
  }
  return true;
}

void main() {
  print(validPalindrome('abca'));
}

#include <iostream>
#include <string>
using namespace std;

bool isPal(const string& s, int lo, int hi) {
    while (lo < hi) {
        if (s[lo] != s[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}

bool validPalindrome(const string& s) {
    int lo = 0, hi = s.size() - 1;
    while (lo < hi) {
        if (s[lo] != s[hi]) {
            return isPal(s, lo + 1, hi) || isPal(s, lo, hi - 1);
        }
        lo++;
        hi--;
    }
    return true;
}

int main() {
    cout << (validPalindrome("abca") ? "true" : "false") << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

int isPal(const char *s, int lo, int hi) {
    while (lo < hi) {
        if (s[lo] != s[hi]) return 0;
        lo++;
        hi--;
    }
    return 1;
}

int validPalindrome(const char *s) {
    int lo = 0, hi = strlen(s) - 1;
    while (lo < hi) {
        if (s[lo] != s[hi]) {
            return isPal(s, lo + 1, hi) || isPal(s, lo, hi - 1);
        }
        lo++;
        hi--;
    }
    return 1;
}

int main() {
    printf("%s\n", validPalindrome("abca") ? "true" : "false");
    return 0;
}