String Problems

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 $O(log(n)$ :

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;
    }
}

Custom Sort String - Medium

This problem gives you 2 strings, one is order and the other is the input.
The order is sorted to some “unknown” order and contains only unique lowercase letters

The goal’s to be able to
Code:

def customSortString(self, order: str, s: str) -> str:
	if len(s) == 1:
		return s
	elif not order or len(order) == 0:
		return s
 
	chars = defaultdict(int)
	# map the count of each char in s
	for ch in s:
		if ch not in chars:
			chars[ch] = 1
		else:
			chars[ch] += 1        
	# build the result
	res = ""
	for c in order:
		if c in chars:
			res += (c * chars[c])
			del chars[c]
	# add remaining items, order doesn't matter
	for k,v in chars.items():
		res+= k*v
	return res   

Maximum Nesting Depth

Given a string containing parenthesis, find the maximum depth of nested parenthesis.
// Meaning the max number of parenthesis nested in another pair of parenthesis
My first intuition was to use a Stack to track the opening a closed parenthesis, but as I solved it I found that’s not needed but helped build the intuition on paper.

Algorithm Breakdown:

1. Init cur variable to count the number of currently nested parenthesis at 0.
2. Init max_depth at 0.
3. Iterate through the string:
   1. If current character is '(', then increment current.
   2. If the current character is ')' then decrement, since that’s a closing pair.
4. Then update the max_depth with current if it’s bigger than the previous value.

I left in the commented out stack code in my solution since it helped me get the idea

Code

def maxDepth(self, s: str) -> int:
	# stack = deque()
	cur = 0
	max_dep = 0
	for ch in s:
		if ch == '(':
			# stack.append(ch)
			cur += 1
		elif ch == ')':
			# stack.pop()
			cur -= 1
		max_dep = max(cur, max_dep) # updated the max with the bigger value
	return max_dep