Valid Palindrome III, DFS, what is my time and space complexity?
tellmeyourstoryman
12

I have my own solution to this problem but I'm not sure what my time complexity is. Could someone weigh in on whether my analysis is correct please? :)

Valid Palindrome III

Given a string s and an integer k, return true if s is a k-palindrome.
A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Example 1:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:
Input: s = "abbababa", k = 1
Output: true

Constraints:
1 <= s.length <= 1000
s consists of only lowercase English letters.
1 <= k <= s.length

function isValidPalindrome(s, k){
    return dfs(s,k)
}


/**
Time Complexity: O(n*2^k)
    - In the worst case there are k amount of characters we need to remove and in each case we explore two possible subcases of either a removal of left or a removal of night. 
    - In each of the subcases we would iterate at most n times
Space Complexity: O(n) 
 - Let h be the height of the levels we recurse in the worst case k = n which means we recurve n times.
*/

function dfs (s, k) {
     if (s.length < k) return true;
    
    
    const descendMatches = (first, second) => { // takes two indexes, returns when they don't match or crossed paths 
        while (first <= second && s[first] === s[second]){
            first++; second--;
        }
        return [first, second];
    }
    
    const memo = new Map();
    const dfs = (first, second, count) => {
        if (first === second) return first === second;
        [first, second] = descendMatches(first, second); // try going as far as we can without encountering none match
        if (first > second) return true; // if the pointers cross the nwe know that this string is valid
        else if (count < k) // if we still have remaining characters that we can delete 
            if (dfs(first + 1, second, count + 1) || dfs(first, second -1, count + 1)) 
                return true;
        return false;
    }
    
    return dfs(0, s.length - 1, 0);
};

// console.log("'', 0 => true, ", isValidPalindrome('', 0))
// console.log("'a', 0 => true", isValidPalindrome('a', 0))
// console.log("'ab', 0 => false", isValidPalindrome('ab', 0))
// console.log("'ab', 1 => true", isValidPalindrome('ab', 1))
// console.log("'ab', 2 => true", isValidPalindrome('ab', 2))
// console.log("'aba', 2 => true", isValidPalindrome('aba', 2))
// console.log("'aba', 2 => true", isValidPalindrome('aba', 2))
// console.log("'abca', 2 => true", isValidPalindrome('abca', 2))
// console.log("'adbca', 2 => true", isValidPalindrome('adbca', 2))
// console.log("'adbca', 1 => false", isValidPalindrome('adbca', 1))
// console.log("'abcd', 4 => true", isValidPalindrome('abcd', 4))
// console.log("'aaacddd', 6 => true", isValidPalindrome('aaacddd', 6))
Comments (0)