Buckets:
| tags: | |
| - notes | |
| - dynamic-programming | |
| - 1d-dynamic-programming | |
| patterns: | |
| ### [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) EASY | |
| You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top? | |
| ``` | |
| Input: n = 2 | |
| Output: 2 | |
| Explanation: There are two ways to climb to the top. | |
| 1. 1 step + 1 step | |
| 2. 2 steps | |
| Input: n = 3 | |
| Output: 3 | |
| Explanation: There are three ways to climb to the top. | |
| 1. 1 step + 1 step + 1 step | |
| 2. 1 step + 2 steps | |
| 3. 2 steps + 1 step | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of steps. | |
| #### Solution | |
| - **Brute Force** | |
| 1. Brute force solution is to solve for all possible steps starting from 0, jump 1 or 2 steps. | |
| 2. Base case is reaching the step outside the range `n` . When we reach a step beyond or on `n` , return 1 if we are at `n` or 0 if we are beyond `n` . If we are beyond `n` returning 0 indicates that we have reached outside the destination and that that step is invalid. | |
| ```python | |
| class Solution: | |
| def climbStairs(self, n: int) -> int: | |
| def helper(i): | |
| if i >= n: | |
| return int(i == n) | |
| return helper(i + 1) + helper(i + 2) | |
| return helper(0) | |
| ``` | |
| TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$ | |
| - **Memoization** | |
| 1. Same as brute force, but adding a cache to store the repeating cases | |
| 2. Add a cache dictionary to store the distinct ways for each step, and use it when the case is revisited. | |
| ```python | |
| class Solution: | |
| def climbStairs(self, n: int) -> int: | |
| cache = {} | |
| def helper(i): | |
| if i >= n: | |
| return int(i == n) | |
| if i in cache: | |
| return cache[i] | |
| cache[i] = helper(i + 1) + helper(i + 2) | |
| return cache[i] | |
| return helper(0) | |
| ``` | |
| TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$ | |
| ### [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) EASY | |
| You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index `0`, or the step with index `1`. Return _the minimum cost to reach the top of the floor_. | |
| ``` | |
| Input: cost = [10,15,20] | |
| Output: 15 | |
| Explanation: You will start at index 1. | |
| - Pay 15 and climb two steps to reach the top. | |
| The total cost is 15. | |
| Input: cost = [1,100,1,1,1,100,1,1,100,1] | |
| Output: 6 | |
| Explanation: You will start at index 0. | |
| - Pay 1 and climb two steps to reach index 2. | |
| - Pay 1 and climb two steps to reach index 4. | |
| - Pay 1 and climb two steps to reach index 6. | |
| - Pay 1 and climb one step to reach index 7. | |
| - Pay 1 and climb two steps to reach index 9. | |
| - Pay 1 and climb one step to reach the top. | |
| The total cost is 6. | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of steps on the staircase. | |
| #### Solution | |
| - **Brute Force** | |
| 1. Using a recursion approach, we can visit all possible steps to check for best minimum cost. | |
| 2. We start from 0 and move bottom to reach the final destination. Base case would be when we reach beyond the stairs. In that case, 0 will be returned, indicating that path is not possible. | |
| 3. For all other cases, current + 1 and current + 2 steps will be visited and only the minimum of those two will be considered. With that the cost for current step will be added. | |
| 4. When the recursion has finished for 0, for 1 the same will be done and the minimum of both will be returned. | |
| ```python | |
| class Solution: | |
| def minCostClimbingStairs(self, cost: List[int]) -> int: | |
| size = len(cost) | |
| def helper(i): | |
| if i >= size: | |
| return 0 | |
| return min(helper(i + 1), helper(i + 2)) + cost[i] | |
| return min(helper(0), helper(1)) | |
| ``` | |
| TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$ | |
| - **Memoization** | |
| 1. Same as above, using recursion to cover all possible steps, but caching the visited steps for reference. | |
| ```python | |
| class Solution: | |
| def minCostClimbingStairs(self, cost: List[int]) -> int: | |
| cache = {} | |
| n = len(cost) | |
| def helper(i): | |
| if i >= n: | |
| return 0 | |
| if i in cache: | |
| return cache[i] | |
| cache[i] = min(helper(i + 1), helper(i + 2)) + cost[i] | |
| return cache[i] | |
| return min(helper(0), helper(1)) | |
| ``` | |
| TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$ | |
| - **Optimised** | |
| It's an iterative process of starting either from the end or from the beginning and comparing the cost of previous two steps. The answer would be the minimum of latest two prices. | |
| ```python | |
| class Solution: | |
| def minCostClimbingStairs(self, cost: List[int]) -> int: | |
| size = len(cost) | |
| dp = [0] * (size + 1) | |
| dp[-1], dp[-2] = 0, cost[-1] | |
| for i in range(size - 2, -1, -1): | |
| dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i] | |
| return min(dp[0], dp[1]) | |
| ``` | |
| **OR** | |
| ```python | |
| class Solution: | |
| def minCostClimbingStairs(self, cost: List[int]) -> int: | |
| size = len(cost) | |
| dp = [0] * (size + 1) | |
| dp[-1], dp[-2] = 0, cost[-1] | |
| for i in range(size - 2, -1, -1): | |
| dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i] | |
| return min(dp[0], dp[1]) | |
| ``` | |
| ### [Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/description/) MEDIUM | |
| Given a `m x n` `grid` filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. | |
| **Note:** You can only move either down or right at any point in time. | |
| **Example 1:** | |
|  | |
| ``` | |
| Input: grid = [[1,3,1],[1,5,1],[4,2,1]] | |
| Output: 7 | |
| Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum. | |
| ``` | |
| ``` | |
| Example 2: | |
| Input: grid = [[1,2,3],[4,5,6]] | |
| Output: 12 | |
| ``` | |
| #### Solution | |
| First, we need to create a 2D cache grid to hold the traversal results, and fill it with -1. We start from the bottom right of the grid. Traverse the up and left cell of the bottom right cell, recursively and store the minimum of them in the cache cell in that row and column index. The loop breaking conditions are: | |
| - If the top-left cell is reached, return its value. | |
| - If we reach beyond the grid, return a huge number, indicating we reached beyond the grid. | |
| Lastly, if the cell was already visited, return its value from cache. | |
| ```python | |
| class Solution: | |
| def minPathSum(self, grid: List[List[int]]) -> int: | |
| ROW, COL = len(grid), len(grid[0]) | |
| dp = [[-1 for _ in range(COL)] for _ in range(ROW)] | |
| return self.helper(ROW - 1, COL - 1, dp, grid) | |
| def helper(self, i, j, _dp, grid): | |
| if i == 0 and j == 0: | |
| return grid[0][0] | |
| if i < 0 or j < 0: | |
| return 9999999 | |
| if _dp[i][j] != -1: | |
| return _dp[i][j] | |
| up = grid[i][j] + self.helper(i - 1, j, _dp, grid) | |
| left = grid[i][j] + self.helper(i, j - 1, _dp, grid) | |
| _dp[i][j] = min(up, left) | |
| return _dp[i][j] | |
| ``` | |
| Similarly, it can be solved in top-down approach too. | |
| ```python | |
| class Solution: | |
| def minPathSum(self, grid: List[List[int]]) -> int: | |
| ROW, COL = len(grid), len(grid[0]) | |
| dp = [[-1 for _ in range(COL)] for _ in range(ROW)] | |
| def helper(i, j): | |
| if i == ROW - 1 and j == COL - 1: | |
| return grid[i][j] | |
| if i >= ROW or j >= COL: | |
| return int(1e9) | |
| if dp[i][j] != -1: | |
| return dp[i][j] | |
| down = grid[i][j] + helper(i + 1, j) | |
| right = grid[i][j] + helper(i, j + 1) | |
| dp[i][j] = min(down, right) | |
| return dp[i][j] | |
| return helper(0, 0) | |
| ``` | |
| ### Coin Change | |
| You are given an integer array `coins` representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer `amount` representing a target amount of money. | |
| Return the fewest number of coins that you need to make up the _exact_ target amount. If it is impossible to make up the amount, return `-1`. | |
| You may assume that you have an unlimited number of each coin. | |
| **Example 1:** | |
| ```java | |
| Input: coins = [1,5,10], amount = 12 | |
| Output: 3 | |
| ``` | |
| Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available. | |
| **Example 2:** | |
| ```java | |
| Input: coins = [2], amount = 3 | |
| Output: -1 | |
| ``` | |
| Explanation: The amount of 3 cannot be made up with coins of 2. | |
| **Example 3:** | |
| ```java | |
| Input: coins = [1], amount = 0 | |
| Output: 0 | |
| ``` | |
| Explanation: Choosing 0 coins is a valid way to make up 0 | |
| #### Solution | |
| The easiest approach is bottom up DP. We need to have an array of length `amount + 1` to store the no of coins required to sum up to amount `a`, where `a` $\in$ `[1, amount]`. Loop over all possible `a - c` combinations and fill/update the values in the array. For a particular combination of `a - c` the no of coins required to get a sum of `a - c` is `1 + dp[a - c]`. We compare this with existing value of `dp[a- c]` and chose minimum of the two. | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution with `O(n * t)` time and `O(t)` space, where `n` is the number of coins and `t` is the given amount. | |
| ```python | |
| class Solution: | |
| def coinChange(self, coins: List[int], amount: int) -> int: | |
| tabu = [amount + 1] * (amount + 1) | |
| tabu[0] = 0 | |
| for a in range(1, amount + 1): | |
| for c in coins: | |
| if a - c >= 0: | |
| tabu[a] = min(tabu[a], 1 + tabu[a - c]) | |
| print(tabu) | |
| return tabu[amount] if tabu[amount] != amount + 1 else -1 | |
| ``` | |
| ### Edit Distance | |
| You are given two strings `word1` and `word2`, each consisting of lowercase English letters. | |
| You are allowed to perform three operations on `word1` an unlimited number of times: | |
| - Insert a character at any position | |
| - Delete a character at any position | |
| - Replace a character at any position | |
| Return the minimum number of operations to make `word1` equal `word2`. | |
| **Example 1:** | |
| ```java | |
| Input: word1 = "monkeys", word2 = "money" | |
| Output: 2 | |
| ``` | |
| Explanation: | |
| `monkeys` -> `monkey` (remove `s`) | |
| `monkey` -> `monkey` (remove `k`) | |
| **Example 2:** | |
| ```java | |
| Input: word1 = "neatcdee", word2 = "neetcode" | |
| Output: 3 | |
| ``` | |
| Explanation: | |
| `neatcdee` -> `neetcdee` (replace `a` with `e`) | |
| `neetcdee` -> `neetcde` (remove last `e`) | |
| `neetcde` -> `neetcode` (insert `o`) | |
| #### Solution | |
| ![[edit-distance-sol.png]] | |
| We create a 2D grid to store the minimum changes required to get the `word2` string. The size of the grid will be `(len(word1) + 1) * (len(word2) + 1)`. The last row and column of the grid will be the size of the sub-string from that column and row index, indicating that if the one string is empty, it would take "length of the other string" operations to get that string. We do a bottom-up traversal to get the minimum steps required to get the result string. There are two conditions to decide whether to insert, update or delete. | |
| - If the character at the positions are same, it is to be skipped. | |
| - else, the minimum of the 3 operations, insert, delete and update is to be considered and an additional cost is to be added. | |
| ```python | |
| class Solution: | |
| def minDistance(self, word1: str, word2: str) -> int: | |
| dp = [[ | |
| float("inf") for _ in range(len(word2) + 1) | |
| ] for _ in range(len(word1) + 1) | |
| ] | |
| for i in range(len(word1) + 1): | |
| dp[i][-1] = len(word1) - i | |
| for i in range(len(word2) + 1): | |
| dp[-1][i] = len(word2) - i | |
| for i in range(len(word1) - 1, -1, -1): | |
| for j in range(len(word2) - 1, -1, -1): | |
| if word1[i] == word2[j]: | |
| dp[i][j] = dp[i + 1][j + 1] | |
| else: | |
| dp[i][j] = min( | |
| dp[i + 1][j], | |
| dp[i][j + 1], | |
| dp[i + 1][j + 1] | |
| ) + 1 | |
| return dp[0][0] | |
| ``` | |
| ### Decode Ways MEDIUM | |
| A string consisting of uppercase english characters can be encoded to a number using the following mapping: | |
| ```java | |
| 'A' -> "1" | |
| 'B' -> "2" | |
| ... | |
| 'Z' -> "26" | |
| ``` | |
| To **decode** a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, `"1012"` can be mapped into: | |
| - `"JAB"` with the grouping `(10 1 2)` | |
| - `"JL"` with the grouping `(10 12)` | |
| The grouping `(1 01 2)` is invalid because `01` cannot be mapped into a letter since it contains a leading zero. | |
| Given a string `s` containing only digits, return the number of ways to **decode** it. You can assume that the answer fits in a **32-bit** integer. | |
| **Example 1:** | |
| ```java | |
| Input: s = "12" | |
| Output: 2 | |
| Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). | |
| ``` | |
| **Example 2:** | |
| ```java | |
| Input: s = "01" | |
| Output: 0 | |
| ``` | |
| Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter. | |
| #### Solution | |
| Think of decoding as breaking the string into valid 1- or 2-digit groups, each mapping to a letter. Use recursion with memoization: At each step, try decoding 1 digit (if valid) and 2 digits (if between "10"-"26"). Sum up the **ways**, caching results for efficiency. | |
| ```python | |
| class Solution: | |
| def numDecodings(self, s: str) -> int: | |
| cache = {len(s):1} | |
| def helper(i): | |
| if i in cache: | |
| return cache[i] | |
| if s[i] == "0": | |
| return 0 | |
| res = helper(i + 1) | |
| if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i + 1] in "0123456")): | |
| res += helper(i + 2) | |
| cache[i] = res | |
| return cache[i] | |
| return helper(0) | |
| ``` | |
| ### Maximum Product Subarray MEDIUM | |
| Given an integer array `nums`, find a **subarray** that has the largest product within the array and return it. | |
| A **subarray** is a contiguous non-empty sequence of elements within an array. | |
| You can assume the output will fit into a **32-bit** integer. | |
| **Example 1:** | |
| ```java | |
| Input: nums = [1,2,-3,4] | |
| Output: 4 | |
| ``` | |
| **Example 2:** | |
| ```java | |
| Input: nums = [-2,-1] | |
| Output: 2 | |
| ``` | |
| #### Solution | |
| We are using Kadane's algorithm here, which is kind of DP and Greedy Algorithm. Loop over each element in the list and calculate the maximum and minimum possible product till that position. Keep a result variable to store the result by modifying it whenever the max product increases. | |
| ```python | |
| class Solution: | |
| def maxProduct(self, nums: List[int]) -> int: | |
| res = nums[0] | |
| curr_min, curr_max = 1, 1 | |
| for i, num in enumerate(nums): | |
| temp = curr_max * num | |
| curr_max = max(num * curr_max, num * curr_min, num) | |
| curr_min = min(temp, num * curr_min, num) | |
| res = max(res, curr_max) | |
| return res | |
| ``` | |
| ### Word Break | |
| Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of dictionary words. | |
| You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique. | |
| **Example 1:** | |
| ```java | |
| Input: s = "neetcode", wordDict = ["neet","code"] | |
| Output: true | |
| ``` | |
| Explanation: Return true because "neetcode" can be split into "neet" and "code". | |
| **Example 2:** | |
| ```java | |
| Input: s = "applepenapple", wordDict = ["apple","pen","ape"] | |
| Output: true | |
| ``` | |
| Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words. | |
| **Example 3:** | |
| ```java | |
| Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"] | |
| Output: false | |
| ``` | |
| #### Solution | |
| Think of the problem as checking if you can build the string `s` by repeatedly "cutting off" dictionary words from its start. Use dynamic programming: | |
| - Create a boolean array `dp`, where `dp[i]` means "s[i:] can be segmented." | |
| - Start from the end of `s`; at each position, try every word in `wordDict`. | |
| - If a word matches the sub-string at `s[i:]` and the remaining part can be segmented (`dp[i + len(word)]`), mark `dp[i]` as `True`. | |
| - Use early exit to optimize. | |
| This approach efficiently checks all segmentations and avoids recomputation. | |
| ```python | |
| class Solution: | |
| def wordBreak(self, s: str, wordDict: List[str]) -> bool: | |
| dp = [False] * (len(s) + 1) | |
| dp[len(s)] = True | |
| for i in range(len(s) - 1, -1, -1): | |
| for w in wordDict: | |
| if len(s) >= (i + len(w)) and s[i: i + len(w)] == w: | |
| dp[i] = dp[i + len(w)] | |
| if dp[i]: | |
| break | |
| return dp[0] | |
| ``` | |
| ### Longest Increasing Subsequence | |
| Given an integer array `nums`, return the _length_ of the longest strictly _increasing_ subsequence. | |
| A **subsequence** is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters. | |
| - For example, `"cat"` is a subsequence of `"crabt"`. | |
| **Example 1:** | |
| ```java | |
| Input: nums = [9,1,4,2,3,3,7] | |
| Output: 4 | |
| ``` | |
| Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4. | |
| **Example 2:** | |
| ```java | |
| Input: nums = [0,3,1,3,2,3] | |
| Output: 4 | |
| ``` | |
| #### Solution | |
| Treat the array as a sequence where for each position `i`, you want to know the length of the longest increasing sub-sequence starting at `i`. Use dynamic programming: | |
| - For each index, look forward to all higher-index elements larger than `nums[i]` and update `dp[i]` accordingly. | |
| - The answer is the maximum in `dp`. This captures all possible sub-sequences efficiently by building solutions for smaller sub-arrays first. | |
| ```python | |
| class Solution: | |
| def lengthOfLIS(self, nums: List[int]) -> int: | |
| dp = [1] * len(nums) | |
| dp[len(nums) - 1] = 1 | |
| for i in range(len(nums) - 1, -1, -1): | |
| for j in range(i + 1, len(nums)): | |
| if nums[i] < nums[j]: | |
| dp[i] = max(dp[i], 1 + dp[j]) | |
| return max(dp) | |
| ``` | |
| ### **House Robber [Leetcode](https://leetcode.com/problems/house-robber/description/) MEDIUM** | |
| You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**. Given an integer array `nums` representing the amount of money of each house, return _the maximum amount of money you can rob tonight **without alerting the police**_. | |
| **Example 1:** | |
| ``` | |
| Input: nums = [1,2,3,1] | |
| Output: 4 | |
| Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). | |
| Total amount you can rob = 1 + 3 = 4. | |
| Input: nums = [2,7,9,3,1] | |
| Output: 12 | |
| Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). | |
| Total amount you can rob = 2 + 9 + 1 = 12. | |
| ``` | |
| #### Solution | |
| - **Brute Force** | |
| 1. Start from the 0th house, move to `i+2` th house or `i+3` th house, chose the max amongst them and add the cost for `i` th house. | |
| 2. Base case would be when we have reached the end of list or have reached beyond the list. | |
| ```python | |
| class Solution: | |
| def rob(self, nums: List[int]) -> int: | |
| n = len(nums) | |
| def helper(i): | |
| if i >= n: | |
| return 0 | |
| return max(helper(i + 2), helper(i + 3)) + nums[i] | |
| return max(helper(0), helper(1)) | |
| ``` | |
| - **Optimized (Memoization)** | |
| 1. Add a cache dictionary to store visited cases and use them when they are visited again. | |
| ```python | |
| class Solution: | |
| def rob(self, nums: List[int]) -> int: | |
| n = len(nums) | |
| cache = {} | |
| def helper(i): | |
| if i >= n: | |
| return 0 | |
| if i in cache: | |
| return cache[i] | |
| cache[i] = max(helper(i + 2), helper(i + 3)) + nums[i] | |
| return cache[i] | |
| return max(helper(0), helper(1)) | |
| ``` | |
| ### House Robber II (Leetcode) MEDIUM | |
| You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbours. You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were _both_ broken into. Return the _maximum_ amount of money you can rob without alerting the police. | |
| ``` | |
| Input: nums = [3,4,3] | |
| Output: 4 | |
| Input: nums = [2,9,8,3,6] | |
| Output: 15 | |
| # Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15. | |
| ``` | |
| > [!info] Time and Space Complexity | |
| > You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of houses. | |
| #### Solution | |
| - **Optimized** (**Memoization**) | |
| The circular house constraint means if you rob house 0, you can't rob house n-1, so break this into two linear sub-problems: rob houses 0 to n-2 OR rob houses 1 to n-1. Use a flag parameter to track if house 0 was robbed - when flag = True, you cannot rob the last house. The recursion explores rob/skip decisions at each house while respecting this circular constraint, and the final answer is max(helper(0, True), helper(1, False)) to try both scenarios. | |
| ```python | |
| class Solution: | |
| def rob(self, nums: List[int]) -> int: | |
| size = len(nums) | |
| if size == 1: | |
| return nums[size - 1] | |
| cache = {} | |
| def helper(i: int, flag: bool): | |
| if i >= size or (flag and i == size - 1): | |
| return 0 | |
| if (i, flag) in cache: | |
| return cache[(i, flag)] | |
| cache[(i, flag)] = max( | |
| helper(i + 1, flag), | |
| helper(i + 2, flag or i == 0) + nums[i], | |
| ) | |
| return cache[(i, flag)] | |
| return max(helper(0, True), helper(1, False)) | |
| ``` | |
| ### Longest Palindromic Sub-string MEDIUM | |
| Given a string `s`, return the longest sub-string of `s` that is a _palindrome_. A **palindrome** is a string that reads the same forward and backward. If there are multiple palindromic sub-strings that have the same length, return any one of them. | |
| **Example 1:** | |
| ```java | |
| Input: s = "ababd" | |
| Output: "bab" | |
| ``` | |
| Explanation: Both "aba" and "bab" are valid answers. | |
| **Example 2:** | |
| ```java | |
| Input: s = "abbc" | |
| Output: "bb" | |
| ``` | |
| #### Solution | |
| A non-DP solution will be to start from index 0 and spread out, checking all possible palindromes in the string. Then choosing the longest palindrome of them. | |
| ```python | |
| class Solution: | |
| def longestPalindrome(self, s: str) -> str: | |
| self.max_string = s[0] | |
| self.max_len = 1 | |
| def check_palindrome(i, j): | |
| while i >= 0 and j < len(s) and s[i] == s[j]: | |
| if len(s[i:j + 1]) > self.max_len: | |
| self.max_len = j - i + 1 | |
| self.max_string = s[i:j + 1] | |
| i -= 1 | |
| j += 1 | |
| for i in range(len(s)): | |
| l, r = i, i | |
| check_palindrome(l, r) | |
| l, r = i, i + 1 | |
| check_palindrome(l, r) | |
| return self.max_string | |
| ``` | |
Xet Storage Details
- Size:
- 23.4 kB
- Xet hash:
- 5f5c33ed5c8f806932be15680dccd55abcd6789b169828bc52a585292fa7d592
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.