Strings - Question 6 Valid Palindrome (Easy)

subproblem?

sub problem is a problem we have to solve along the way to solving the main problem!

Palindrome?

palindrome is a string that reads the same forwards and backwards

1. we set two pointers and one pointer starts from the beginning, the other pointer starts from the end of the sentence, compare those characters
2. we set two pointers from the center of the sentence, and one pointer goes towards the beginning of the sentence, the other pointer goes towards the end of the sentence, compare those characters
3. we reverse the whole string and compare original strings and reversed strings match

Question

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring case sensitivity.

Verify the constraints

• we can ignore the constraints because the question is very clear.

Write out some test cases

1. "aabaa" //true
2. "aabbaa" //true
3. "abc" //false
4. "a" //true
5. "" //true
6. "A man, a plan, a canal:Panama" //true

Figure out a solution without code

• remove all the characters that are not alphanumeric characters
• reverse the string
• compare the whole string

Write out our solution in code

Solution 1

function isValidPalindrome(s){
 s = s.toLowerCase();
  let regex = /[^a-z0-9]/g
  for(let i = 0; i < s.length; i++){
    if(!s[i].match(regex)){
      s = s.slice(0, i) + s.slice(i+1)
      i--;
    }
  }
  let i = 0;
  let j = s.length - 1;
  while(i < j){
    if(s[i] !== s[j]){
      return false;
    }
    i++;
    j--;
  }
  return true;
}

console.log(isValidPalindrome("aabaa"))
console.log(isValidPalindrome("aabbaa"))
console.log(isValidPalindrome("abc"))
console.log(isValidPalindrome("a"))
console.log(isValidPalindrome(""))
console.log(isValidPalindrome(" A man, a plan, a canal:Panama"))
console.log(isValidPalindrome("aabaa"))

Solution 2 (More advanced version of solution 1 - regex optimization)

function isValidPalindrome(s){
 s = s.toLowerCase();
  let regex = /[^a-z0-9]/g
 s = s.replace(regex, "");
  let i = 0;
  let j = s.length - 1;
  while(i < j){
    if(s[i] !== s[j]){
      return false;
    }
    i++;
    j--;
  }
  return true;
}

console.log(isValidPalindrome("aabaa"))
console.log(isValidPalindrome("aabbaa"))
console.log(isValidPalindrome("abc"))
console.log(isValidPalindrome("a"))
console.log(isValidPalindrome(""))
console.log(isValidPalindrome(" A man, a plan, a canal:Panama"))
console.log(isValidPalindrome("aabaa"))

Analyze Space and Time Complexity

• Solution 1
  • Time Complexity : O(N)
  • Space Complexity : O(1)
• Solution 2
  • Time Complexity : O(N)
  • Space Complexity : O(1)

Developing References

Developing Report

2025-01-22 - Strings - Question 6 Valid Palindrome (Easy) Report
2025-01-22 - Developing Daily Report
2025-01-4th - Developing Weekly Report