Abdu's Garden

String Problems

3 min read

They’re great.

Valid Palindromes - Easy

This version is only concerned with alphanumeric characters (letters and numbers) so you need to strip and trim of anything else. There’s a few ways to do this, I used Recursion cuz I’m a smartass. Idea:

  1. Base case: when length of string is 1 or less → return True.
  2. Check if first and last characters are the NOT the same, then return False.
  3. Else, do the recursive call on the substring, work your way in from the outside, pinching both ends one character at a time. Example:
class Solution {
    /**
    Prepare the string by removing all non alphanumeric characters.
     */
    public String prepareString(String input){
        return input.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    }
 
    public boolean checkPalindrome(String input) {
        // String tidyStr = prepareString(s);
        if(input.length() <= 1){
            return true;
        }
        else{
            // System.out.println(tidyStr);
            if(input.charAt(0) != input.charAt(input.length() - 1)){
                return false;
            }
            else {
                return checkPalindrome(input.substring(1, input.length() - 1));
            }
        }
    }
 
	// Did this because only wanted to preprocess once...
    public boolean isPalindrome(String s){
        String tidyStr = prepareString(s);
        return checkPalindrome(tidyStr);
    }
}

This recursive solution is VERY slow.

Whereas this one is :

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) <= 1:
            return True
 
        formatted_input = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
        length = len(formatted_input)
 
        index = 0
        while index < len(formatted_input) // 2:
            if formatted_input[index] != formatted_input[length - index - 1]:
                return False
            index += 1
        return True

Longest Palindrome - Easy

Given a string s that’s made up of upper and lowercase characters, find the longest possible palindrome that can be made from them.

don't actually build the palindromes

Instead it’s all about the frequency, you want to check which characters are even and which are odd. // Highly recommend trying some examples on paper

Breakdown

  • Using either a HashMap or the character-index array trick seen in some other string problems, count the frequency of each char.
  • while doing that, check if the new frequency is even, if so increment the max length by two, since that means we can add those two new instances to the palindrome.
  • Then when all the counting is done, check if there are any with an odd frequency, if some increment the max length and break. This works because previously, we’ve incremented by 2 at each step if they’re even.

Code:

class Solution {
    public int longestPalindrome(String s) {
         if (s.length() <= 1) return s.length();
 
        int maxLength = 0;
        int[] freqs = new int[52];
        char[] chars = s.toCharArray();
 
        for (char c : chars) {
            if (Character.isLowerCase(c)) {
                freqs[c - 'a']++;
                if (freqs[c - 'a'] % 2 == 0) maxLength += 2;
            }
            if (Character.isUpperCase(c)) {
                freqs[c - 'A' + 26]++;
                if (freqs[c - 'A' + 26] % 2 == 0) maxLength += 2;
            }
        }
        for (int i : freqs) {
            if (i % 2 == 1) {
                maxLength++;
                break;
            }
        }
        return maxLength;
    }
}

Graph View

Backlinks