## LC 91. Decode Ways A message containing letters from A-Z can be encoded into numbers using the following mapping: ``` 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" ``` To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into: `"AAJF"` with the grouping (`1 1 10 6`) `"KJF"` with the grouping (`11 10 6`) Note that the grouping (`1 11 06`) is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`. Given a string s containing only digits, return the number of ways to decode it. ### Recursive DP Approach: We will use dp to solve this problem. dp[i] stores no. of ways input[i:n] can be decoded. There are two ways each digit can be mapped. Once just considering the digit itself and once with its next digit. If we consider only the digit, then any digit between 1-9 can be mapped. And if we consider with next digit, then it can be mapped between 10-26. For every index, only current index and next index plays a role in calculating the number of ways to decode the digit at current index. While considering only current digit, if the digit is in between 1-9, then, we call it for the sub-problem index+1 and add it to the no. of ways for current index. And while considering with next digit, if the digits is in between 10-26, then, we call it for the sub-problem index+2 and add it to the no. of ways for current index. **Base Case:** When index >= s.length, return 1. And when the 1st digit in the input string is 0, return 0. ```java class Solution1 { public int numDecodings(String s) { char[] ch = s.toCharArray(); int[] dp = new int[ch.length]; Arrays.fill(dp, -1); return doDp(ch, 0, dp); } private int doDp(char[] ch, int index, int[] dp) { if (index >= ch.length) return 1; else if (index == 0 && ch[index] == '0') return 0; if (dp[index] != -1) return dp[index]; int ways = 0; if (ch[index] - '0' > 0 && ch[index] - '0' <= 9) ways += doDp(ch, index + 1, dp); if (index + 1 < ch.length) { int twoDigit = (ch[index] - '0') * 10 + (ch[index + 1] - '0'); if (twoDigit >= 10 && twoDigit <= 26) ways += doDp(ch, index + 2, dp); } return dp[index] = ways; } } ``` ### Iterative DP Approach: We use the same dp approach. dp[i] stores number of ways input[:i] can be decoded. Since, empty character can be decoded in 1 way, dp[0]=1. And if the 1st digit in the input is 0, then dp[1] = 0, else dp[1]=1. This is because, is the 1st digit is zero, there are zero ways input string input[0] can be decoded. Now, While considering single digit, if the digit is between 1-9, then dp[i] = dp[i-1]. And, while considering with previous digit, dp[i] = dp[i]+dp[i-2]. ```java class Solution { public int numDecodings(String s) { int[] dp = new int[s.length()+1]; dp[0]=1; // Base case - Empty character will have 1 encoding dp[1]=s.charAt(0)=='0'?0:1; // If 1st char is not zero, then only we can have a valid encoding. for(int i=2;i<=s.length();i++){ int current = Integer.parseInt(s.substring(i-1,i)); // Checking for size = 1 int prev = Integer.parseInt(s.substring(i-2,i)); // Checking for size = 2 if(current>0 && current <=9){ dp[i] = dp[i-1]; // for size 1, no of ways i-1 can be decoded } if(prev>=10 && prev<=26){ dp[i] = dp[i]+dp[i-2]; // for size 2, no of ways i-2 can be decoded since on top of that this will be added. } } return dp[s.length()]; } } ``` ## LC 639. Decode Ways II A message containing letters from A-Z can be encoded into numbers using the following mapping: ``` 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" ``` To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into: `"AAJF"` with the grouping `(1 1 10 6)` `"KJF"` with the grouping `(11 10 6)` Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`. In addition to the mapping above, an encoded message may contain the `'*'` character, which can represent any digit from `'1'` to `'9'` (`'0'` is excluded). For example, the encoded message `"1*"` may represent any of the encoded messages `"11", "12", "13", "14", "15", "16", "17", "18", or "19"`. Decoding `"1*"` is equivalent to decoding any of the encoded messages it can represent. Given a string s consisting of digits and `'*'` characters, return the number of ways to decode it. Since the answer may be very large, return it modulo `10^9 + 7`. ### Recursive DP Approach: We will be using dp to solve this problem. dp[i] represents the no. of ways string input[i:] can be decoded into. Each character can either be considered by itself or with its next character. While considered by itself, the character can be either a digit or `"*"`. And while being considered with next element, both characters can be digits, or one of the character is a digit other being `"*"`. Or, both can be `"*"`. 1. When considering single character: - When the character is a digit, `dp[i] = 1 * dp[i+1]` - When the character is a `"*"`, then it can be converted to `1,2,3,4,5,6,7,8,9`, then, `dp[i] = 9 * dp[i+1]` 2. When considering current character with next character: - When both the characters are digit, i.e, 10-26 `dp[i] = 1 * dp[i+2]` - When the current character is a digit and the next character is a `"*"`, And if the current digit is 1, then numbers can be 11-19, so, `dp[i] = 9 * dp[i+2]`. Else if the current digit is 2, then numbers can be `21-26`, so, `dp[i] = 6 * dp[i+2]`. - When the current character is a `"*"`, and next character is a digit, then if next character is `<=6`, then the numbers can be between `11-16` & `21-26`, so, `dp[i] = 2 * dp[i+2]`. Else if next character is `>6`, then numbers can be `11-19`, so, `dp[i] = 1 * dp[i+2]`. - When both characters are `"*"`, numbers can be `11-19` & `21-26`, i.e `15`, so, `dp[i] = 15 * dp[i+2]`. **Base Case:** When index >= s.length, return 1. And when the 1st digit in the input string is 0, return 0. ```java class Solution { private final int M = 1000000007; public int numDecodings(String s) { char[] ch = s.toCharArray(); long[] dp = new long[ch.length]; Arrays.fill(dp, -1); return (int) doDp(0, ch, dp); } private long doDp(int index, char[] ch, long[] dp) { if (index >= ch.length) return 1; else if (index == 0 && ch[index] == '0') return 0; if (dp[index] != -1) return dp[index]; long ways = 0; if (ch[index] == '*') { // Current char is a * ways = (ways + 9 * doDp(index + 1, ch, dp)) % M; } else if (ch[index] - '0' > 0 && ch[index] - '0' <= 9) { // When current character is a digit ways = (ways + doDp(index + 1, ch, dp)) % M; } if (index + 1 < ch.length) { if (ch[index] == '*') { if (ch[index + 1] == '*') { // When both chars are * ways = (ways + 15 * doDp(index + 2, ch, dp)) % M; } else { // When 1st char is * but second is digit if (ch[index + 1] - '0' <= 6) ways = ways + (2 * doDp(index + 2, ch, dp)) % M; else ways = (ways + doDp(index + 2, ch, dp)) % M; } } else { if (ch[index + 1] == '*') { // 1st char digit, 2nd char * if (ch[index] == '1') { ways = (ways + 9 * doDp(index + 2, ch, dp)) % M; } else if (ch[index] == '2') { ways = (ways + 6 * doDp(index + 2, ch, dp)) % M; } } else { // Both digit int twoDigit = (ch[index] - '0') * 10 + (ch[index + 1] - '0'); if (twoDigit >= 10 && twoDigit <= 26) ways = (ways + doDp(index + 2, ch, dp)) % M; } } } return dp[index] = ways % M; } } ``` ### Iterative DP Approach: The dp concept remains the same as above. dp[i] stores the number of ways to decode the input[:i]. Where dp[0] stores number of ways to decode empty character. dp[1] stores number of ways to decode input[:1]. And dp[n] stores number of ways to decode input[:n]. So, dp[0] = 1, Since, empty character can be decoded in 1 way. It's the base case. If, `input[0]==digit`, `dp[1] = 1`. Else if, `input[0]=='*'`, `dp[1] = 9`, Else if, `input[0]=='0'`, `dp[1] = 0`. Now, for the general case, each character can be considered by itself or in combination with its previous character. 1. When considering single character: - When the character is a digit, `dp[i] = 1 * dp[i-1]` - When the character is a `"*"`, then it can be converted to `1,2,3,4,5,6,7,8,9`, then, `dp[i] = 9 * dp[i-1]` 2. When considering current character with next character: - When both the characters are digit, i.e, 10-26 `dp[i] = 1 * dp[i-2]` - When the current character is a digit and the next character is a `"*"`, And if the current digit is 1, then numbers can be 11-19, so, `dp[i] = 9 * dp[i-2]`. Else if the current digit is 2, then numbers can be `21-26`, so, `dp[i] = 6 * dp[i-2]`. - When the current character is a `"*"`, and next character is a digit, then if next character is `<=6`, then the numbers can be between `11-16` & `21-26`, so, `dp[i] = 2 * dp[i-2]`. Else if next character is `>6`, then numbers can be `11-19`, so, `dp[i] = 1 * dp[i-2]`. - When both characters are `"*"`, numbers can be `11-19` & `21-26`, i.e `15`, so, `dp[i] = 15 * dp[i-2]`. ```java class Solution { private final int M = 1000000007; public int numDecodings(String s) { char[] ch = s.toCharArray(); long[] dp = new long[ch.length + 1]; dp[0] = 1; if (ch[0] == '0') { dp[1] = 0; } else if (ch[0] == '*') { dp[1] = 9; } else { dp[1] = 1; } for (int i = 2; i <= ch.length; i++) { dp[i] = ch[i - 1] == '*' ? (dp[i - 1] * 9) % M : (ch[i - 1] - '0' > 0 && ch[i - 1] - '0' <= 9 ? dp[i - 1] : 0); if (ch[i - 2] == '*') { if (ch[i - 1] == '*') dp[i] += (15 * dp[i - 2]) % M; // Both chars are * else if (ch[i - 1] - '0' <= 6) dp[i] += (2 * dp[i - 2]) % M; // previous char is *, current char is digit <=6 else dp[i] += dp[i - 2]; // previous char is *, current char is digit > 6. } else if (ch[i - 2] == '1') { if (ch[i - 1] == '*') dp[i] += (9 * dp[i - 2]) % M; // previous char is 1, and current char is *. else dp[i] += dp[i - 2]; // previous char is 1, and current char is digit. } else if (ch[i - 2] == '2') { if (ch[i - 1] == '*') dp[i] += (6 * dp[i - 2]) % M; // previous char is 2, and current char is *. else if (ch[i - 1] - '0' <= 6) dp[i] += dp[i - 2]; // previous char is 2, and current char is digit. } } return (int) (dp[ch.length] % M); } } ``` ## LC 139. 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 one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. ### Recursive DP Approach: We will use dp to solve this. dp[i] stores whether it is possible to segment s[i:] into space-separated sequence of one or more dictionary words. Empty string can always be segmented into sequence of dictionary words. So, dp[s.length] = true. The idea is, if s[0:i] is a word present in dict and dp[i]=true is precalculated, then dp[0] = true. This is because we know s[i:n] can be segmented into dict word and since s[0:i] is present in the dict, then the whole string is present in the dict. So, starting from index 0 to index n-1, we check if the substring s[0:i] is present in the dict. If it's present we recursively try to solve it for the rest of the string s[i:n]. Generally, It iterates from the startingIndex + 1 to the end of the string. For each iteration, it checks if the substring from the startingIndex to the current index is present in the dict and if calling doDp with the current index as the new starting index returns true. If both conditions are satisfied, it sets dp at the starting index to true and returns true. If none of these conditions are satisfied, it sets dp at the starting index to false and returns false. ```java class Solution { public boolean wordBreak(String s, List wordDict) { Set wordSet = new HashSet<>(wordDict); return doDp(0, s, wordSet, new Boolean[s.length()]); } private boolean doDp(int startIndex, String s, Set dict, Boolean[] dp) { if (startIndex >= s.length()) return true; if (dp[startIndex] != null) return dp[startIndex]; for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) { if (dict.contains(s.substring(startIndex, endIndex)) && doDp(endIndex, s, dict, dp)) { return dp[startIndex] = true; } } return dp[startIndex] = false; } } ``` ## BFS Approach: We can use BFS to solve this problem. If the substring s[0:i] is present in the dict, then we need to check if the rest of the string, i.e, s[i:n] is present in the dict. Then the whole string can be segmented into dict words. So, Initially, we will add index 0 to the BFS queue. Then from index 0 to index i, where i ranges from 1 to n-1, we try to check if s[0:i] is present in the dict. If it is present, then we add all such index i, into the queue. Because now we need to check if s[i:n] is present in the dict. And at any point if the index added to the queue is n. Then that means we have reached the very end of the string s. So, the whole string can be segmented into dict words. We also maintain a visited array, that basically stores if index i is already visited, Since, its a bfs and if a index i is already visited, that means there exists some other combination, such that, s[0:i] is already present in the dict. And, index i is already added to the queue for processing. Adding it again won't do any good. ```java class Solution { public boolean wordBreak(String s, List wordDict) { Queue q = new LinkedList<>(); Set set = new HashSet<>(wordDict); q.offer(0); boolean[] visited = new boolean[s.length() + 1]; visited[0] = true; while (!q.isEmpty()) { int startIndex = q.poll(); if (startIndex == s.length()) return true; for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) { if (!visited[endIndex] && set.contains(s.substring(startIndex, endIndex))) { q.offer(endIndex); visited[endIndex] = true; } } } return false; } } ``` ## LC 140. Word Break II Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. ### Recursive DP Approach: We can use dp to solve this problem. dp[i] stores a list of all the strings that can be formed using the substring s[i:n]. Then dp[n] stores all the strings that can be formed using empty string. So, dp[n] = List.of(""). If, s[i:j] matches a word in the dict, and s[j:n] can also be segmented down into dict words. Then s[i:j] can be appended at the beginning to all the sentence combination retuned by dp[j]. We will try to form every possible substring starting from start_index and ending at end_index, where `start_index+1 <= end_index <= n.` And if that substring matches with words in the dict, then we try to solve it for dp[end_index]. ```java class Solution { public List wordBreak(String s, List wordDict) { Set dict = new HashSet<>(wordDict); List[] dp = new List[s.length() + 1]; return doDp(0, s, dict, dp); } private List doDp(int start, String s, Set dict, List[] dp) { if (start == s.length()) return List.of(""); if (dp[start] != null) return (List) dp[start]; List ans = new ArrayList<>(); for (int end = start + 1; end <= s.length(); end++) { String subs = s.substring(start, end); if (dict.contains(subs)) { List sentences = doDp(end, s, dict, dp); for (int i = 0; i < sentences.size(); i++) { ans.add(subs + (sentences.get(i).isEmpty() ? "" : " ") + sentences.get(i)); } } } return (List) (dp[start] = ans); } } ``` ### Backtrack Approach: We will be using backtracking to solve this problem. We will be keeping a running list, storing all the matched words from the dict so far. And finally when recursion reaches index==n, We join the words to form a sentence and add that sentence to the answer list. We will try to form every possible substring starting from start_index and ending at end_index, where `start_index+1 <= end_index <= n.` And if that substring matches with words in the dict, we add the word to the running list and then we recursively call it for end_index. And when the recursion comes back we remove the added word from the running list. Finally, when it is called for index==n, we know that we have reached the end, so, We join the words to form a sentence and add that sentence to the answer list. This way we try out all valid recursion path that leads to index==n. ```java class Solution { public List wordBreak(String s, List wordDict) { Set dict = new HashSet<>(wordDict); List ans = new ArrayList<>(); List runningList = new ArrayList<>(); backTrack(0, s, dict, ans, runningList); return ans; } private void backTrack(int start, String s, Set dict, List ans, List runningList) { if (start == s.length()) { ans.add(String.join(" ", runningList)); return; } for (int end = start + 1; end <= s.length(); end++) { String word = s.substring(start, end); if (dict.contains(word)) { runningList.add(word); backTrack(end, s, dict, ans, runningList); runningList.remove(runningList.size() - 1); } } } } ``` ## LC 131. Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. ### DP approach without Palindrome DP: We can use dp to solve the problem. dp[i] stores a `List>`, which basically stores all the possible palindrome partition for the string s[i:n]. So, dp[n] stores all the possible palindrome partition for an empty string, which is nothing but a empty list. So, `dp[n]={}`. If s[0:i] forms a palindrome, and if we have all the possible palindrome partition for the string s[i:n], Then by appending s[0:i] at the beginning of all the possible palindrome partition for the string s[i:n], we can get all the possible palindrome partition for the string s[0:n]. So, We will try to form every possible substring starting from start_index and ending at end_index, where `start_index <= end_index < n.` And if that substring is a palindrome, then we append that substring with all the possible palindrome partition for dp[end_index]. This will give us all possible palindromic partition for the string s[start_index:n]. We are using isPalindrome function that checks if the string with specified start and end index is a palindrome or not. ```java class Solution { public List> partition(String s) { List>[] dp = new List[s.length()]; return doDp(0, dp, s); } private List> doDp(int index, List>[] dp, String s) { if (index >= s.length()) { return List.of(); } if (dp[index] != null) return dp[index]; List> ans = new ArrayList<>(); for (int i = index; i < s.length(); i++) { if (isPalindrome(s, index, i)) { List> res = doDp(i + 1, dp, s); if (res.isEmpty()) { ans.add(List.of(s.substring(index, i + 1))); } else { for (List r : res) { List t = new ArrayList<>(); t.add(s.substring(index, i + 1)); t.addAll(r); ans.add(t); } } } } return dp[index] = ans; } private boolean isPalindrome(String s, int start, int end) { while (start <= end) { if (s.charAt(start++) != s.charAt(end--)) { return false; } } return true; } } ``` ### DP approach with Palindrome DP: The idea is exactly the same as before. But instead of calculating isPalindrome for every start and end index multiple times. We can use a 2d boolean dp array to store if the string from start_index to end_index forms a palindrome for every possible value of start and end index. For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome. Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j ]should be same and palindrome[i+1][j-1] should be true. So, we will take the string s on both x & y axis of the boolean array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java class Solution { public List> partition(String s) { List>[] dp = new List[s.length()]; boolean[][] palindromeDp = new boolean[s.length()][s.length()]; for(int gap = 0; gap> doDp(int index, List>[] dp, String s, boolean[][] palindromeDp){ if(index >= s.length()){ return List.of(); } if(dp[index]!=null) return dp[index]; List> ans = new ArrayList<>(); for(int i=index; i> res = doDp(i+1, dp, s, palindromeDp); if(res.isEmpty()){ ans.add(List.of(s.substring(index, i+1))); }else{ for(List r: res){ List t =new ArrayList<>(); t.add(s.substring(index, i+1)); t.addAll(r); ans.add(t); } } } } return dp[index] = ans; } private boolean palin(String s, int start, int end, boolean[][] palindromeDp){ return palindromeDp[start][end]; } } ``` ### Backtracking without Palindrome DP: We can use backtrack to solve this problem. We will be keeping a running list that will store the current palindrome partitioned string formed so far from index 0 to index i. We will start from index 0 and for every substring starting from index 0 and ending at index j, we will check if that substring forms a palindrome. If it does, we will add that substring to the running list and recursively call it for index j+1. Now, inside this recursion we will start from index j+1 and for every substring starting from index j+1 and ending at index k, if that forms a palindrome, we add s[j+1:k] to the running list and recurse for index k+1. This continues until index==n, i.e we have reached the end of the string. When we have reached the end of the string, we add the current running list to the answer. And when we return back from the recursion we remove the last added substring from the running list. And look for a bigger substring for palindrome and add it to the running list. And the recursion process continues. We are using isPalindrome function that checks if the string with specified start and end index is a palindrome or not. ```java class Solution { public List> partition(String s) { List> result = new ArrayList<>(); List running = new ArrayList<>(); backtrack(0, s, running, result); return result; } private void backtrack(int start, String s, List runningList, List> result) { if (start >= s.length()) { result.add(new ArrayList<>(runningList)); } for (int end = start; end < s.length(); end++) { if (isPalindrome(s, start, end)) { runningList.add(s.substring(start, end + 1)); backtrack(end + 1, s, runningList, result); runningList.remove(runningList.size() - 1); } } } private boolean isPalindrome(String s, int start, int end) { while (start <= end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end--; } return true; } } ``` ### Backtracking with Palindrome DP(With Palindrome DP Calculated during Backtracking): The Backtracking idea is the same. But instead of checking if a string starting at index i and ending at index j is a palindrome in O(n), we will be using a 2d boolean palindrome dp to store whether the string starting at index i and ending at index j is a palindrome or not. While trying out every possible substring starting at index start_index, the end_index is in the range [start_index to n-1]. So, initially substring is of length 1, which is always true. Then when substring is of size 2, if the edge characters match it is a palindrome. And for substring of size > 3, edges must match and palindromeDp[start_index+1][end_index-1] should be true. The reason why the `dp[start_index+1][end_index-1]` is available even when we are at start_index is because the end always starts from start which is trying to add the letter start to the list. And a single letter is always palindrome, so it recurse for start_index+1. And every possible combination of start_index+1 to end_index-1 gets calculated in this recursion. And When the recursion call returns from start_index+1, the dp[start_index+1][end_index-1] is already available for start. ```java class Solution { public List> partition(String s) { List> result = new ArrayList<>(); List running = new ArrayList<>(); boolean[][] palindromeDp = new boolean[s.length()][s.length()]; backtrack(0, s, running, result, palindromeDp); return result; } private void backtrack(int start, String s, List runningList, List> result, boolean[][] palindromeDp) { if (start >= s.length()) { result.add(new ArrayList<>(runningList)); } for (int end = start; end < s.length(); end++) { if (s.charAt(start)==s.charAt(end) && (end-start<=2 || palindromeDp[start+1][end-1])) { palindromeDp[start][end] = true; runningList.add(s.substring(start, end + 1)); backtrack(end + 1, s, runningList, result,palindromeDp); runningList.remove(runningList.size() - 1); } } } } ``` ### Backtracking with Palindrome DP(With Palindrome DP Precalculated): The idea is very similar to normal backtracking appraoch without palindrome dp. But instead of calculating isPalindrome for every start and end index multiple times. We can use a 2d boolean dp array to store if the string from start_index to end_index forms a palindrome for every possible value of start and end index. For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome. Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j] should be same and palindrome[i+1][j-1] should be true. So, we will take the string s on both x & y axis of the boolean array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java class Solution { public List> partition(String s) { List> result = new ArrayList<>(); List running = new ArrayList<>(); boolean[][] palindromeDp = new boolean[s.length()][s.length()]; for (int gap = 0; gap < s.length(); gap++) { for (int i = 0, j = gap; j < s.length(); i++, j++) { if (gap == 0) palindromeDp[i][j] = true; else if (gap == 1) palindromeDp[i][j] = s.charAt(i) == s.charAt(j); else palindromeDp[i][j] = s.charAt(i) == s.charAt(j) && palindromeDp[i + 1][j - 1]; } } backtrack(0, s, running, result, palindromeDp); return result; } private void backtrack(int start, String s, List runningList, List> result, boolean[][] palindromeDp) { if (start >= s.length()) { result.add(new ArrayList<>(runningList)); } for (int end = start; end < s.length(); end++) { if (palindromeDp[start][end]) { runningList.add(s.substring(start, end + 1)); backtrack(end + 1, s, runningList, result, palindromeDp); runningList.remove(runningList.size() - 1); } } } } ``` ## LC 132. Palindrome Partitioning II Given a string `s`, partition `s` such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. ### Recursive Top Down DP with Palindrome DP precalculated: We can use DP to solve this problem. Here, dp[i] stores the minimum number of required partitions to partition the string s[i:n] into palindromic substrings. And, since, it takes 0 cuts to partition an empty string into palindromic substrings, dp[n] = 0; The dp solution is based on the idea that if s[0:i] forms a palindrome, and if dp[i] = k, then dp[0] = k+1, because if dp[i] requires k minimum cuts and s[0:i] forms a palindrome, then dp[0] will require k+1 cuts. +1 for the s[0:i] palindrome. Now, For any given index i, there can be multiple palindrome starting at index i and ending at some later index. Lets say, There are 3 palindrome strings that starts at i and ends at j1, j2 and j3. Then, dp[i] can either be dp[j1] + 1 or dp[j2] + 1 or dp[j3] + 1. So, we take the minimum of all such possible values of dp[i], because we need to find the minimum number of partitions. Finally, we return dp[0]-1. -1 because if there are k partitions then the cuts will be k-1. During dp call, we need to check if a substring starting at i and ending at j forms a palindrome or not. Here we are using a pre-computed 2d palindromeDp array to store the result of isPalindrome(s, i, j). We can use a 2d boolean dp array to store if the string from start_index to end_index forms a palindrome for every possible value of start and end index. For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome. Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j] should be same and palindromeDp[i+1][j-1] should be true. So, we will take the string s on both x & y axis of the boolean array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java class Solution { public int minCut(String s) { int[] dp = new int[s.length()]; // dp[i] signifies minimum partitions required to create palindrome partition using string s[i:n-1]. boolean[][] palindromeDp = new boolean[s.length()][s.length()]; for (int gap = 0; gap < s.length(); gap++) { for (int i = 0, j = gap; j < s.length(); i++, j++) { if (gap == 0) palindromeDp[i][j] = true; else if (gap == 1) palindromeDp[i][j] = s.charAt(i) == s.charAt(j); else palindromeDp[i][j] = s.charAt(i) == s.charAt(j) && palindromeDp[i + 1][j - 1]; } } Arrays.fill(dp,-1); return dfsWithDp(s, 0, dp, palindromeDp) - 1; // -1 because if there are k partitions then the cuts will be k-1. } private int dfsWithDp(String s, int index, int[] dp, boolean[][] palindromeDp) { if (index >= s.length()) return 0; if(dp[index]!=-1) return dp[index]; int min = Integer.MAX_VALUE; for (int end = index; end < s.length(); end++) { if (palindromeDp[index][end]) { min = Math.min(min, 1 + dfsWithDp(s, end + 1, dp, palindromeDp)); } } return dp[index]=min; } } ``` ### Recursive Top Down DP with Palindrome DP calculated during main DP call: The Dp approach is same as above. The only difference here is how palindrome dp is calculated here. Here, we will be calculating palindromDp during main dp calls. we will be using a 2d boolean palindrome dp to store whether the string starting at index i and ending at index j is a palindrome or not. While trying out every possible substring starting at index start_index, the end_index is in the range [start_index to n-1]. So, initially substring is of length 1, which is always true. Then when substring is of size 2, if the edge characters match it is a palindrome. And for substring of size > 3, edges must match and palindromeDp[start_index+1][end_index-1] should be true. The reason why the `dp[start_index+1][end_index-1]` is available even when we are at start_index is because the end always starts from start which is trying to add the letter start to the list. And a single letter is always palindrome, so it recurse for start_index+1. And every possible combination of start_index+1 to end_index-1 gets calculated in this recursion. And When the recursion call returns from start_index+1, the dp[start_index+1][end_index-1] is already available for start. ```java class SolutionTopDownDPWithPalindromeDP { public int minCut(String s) { int[] dp = new int[s.length()]; // dp[i] signifies minimum partitions required to create palindrome partition using string s[i:n-1]. boolean[][] palindromeDp = new boolean[s.length()][s.length()]; Arrays.fill(dp,-1); return dfsWithDp(s, 0, dp, palindromeDp) - 1; // -1 because if there are k partitions then the cuts will be k-1. } private int dfsWithDp(String s, int index, int[] dp, boolean[][] palindromeDp) { if (index >= s.length()) return 0; if(dp[index]!=-1) return dp[index]; int min = Integer.MAX_VALUE; for (int end = index; end < s.length(); end++) { if (s.charAt(index)==s.charAt(end) && (end-index<=2 || palindromeDp[index+1][end-1])) { palindromeDp[index][end]=true; min = Math.min(min, 1 + dfsWithDp(s, end + 1, dp, palindromeDp)); } } return dp[index]=min; } } ``` ### Iterative Buttom Up DP with Palindrome DP: **Note:** We can calculate the palindromeDp either during dp calculation or precompute it. Both works as shown above. Here, we will be calculating palindromeDp during main dp. But Precompute also works here. So, here we will be using buttom up dp to solve this problem. dp[i] stores the minimum number of palindromic partitions that the string s[i:n] can be partitioned into. We can partition an empty string into 0 palindromic substrings, So, dp[n] = 0; We Iterate from right to left. So, start_index ranges from n-1 to 0, and for every start_index, end_index moves from left to right and ranges from start_index to n-1. For each such combination of start and end index, we check if s[start:end] forms a palindrome. And if it forms a palindrome, then dp[start] = Math.min(dp[start], 1 + dp[end+1]); The dp solution is based on the idea that if s[0:i] forms a palindrome, and if dp[i] = k, then dp[0] = k+1, because if dp[i] requires k minimum cuts and s[0:i] forms a palindrome, then dp[0] will require k+1 cuts. +1 for the s[0:i] palindrome. Now, For any given index i, there can be multiple palindrome starting at index i and ending at some later index. Lets say, There are 3 palindrome strings that starts at i and ends at j1, j2 and j3. Then, dp[i] can either be dp[j1] + 1 or dp[j2] + 1 or dp[j3] + 1. So, we take the minimum of all such possible values of dp[i], because we need to find the minimum number of partitions. Finally, we return dp[0]-1. -1 because if there are k partitions then the cuts will be k-1. ```java class SolutionUsingButtomUpDPWithPalindromeDP { public int minCut(String s) { int[] dp = new int[s.length()+1]; // dp[i] signifies minimum partitions required to create palindrome partition boolean[][] palindromeDp = new boolean[s.length()][s.length()]; Arrays.fill(dp, Integer.MAX_VALUE); dp[s.length()]=0; for(int start=s.length()-1; start>=0;start--){ for(int end = start; end queue = new LinkedList<>(); queue.offer(0); int level = 0; boolean[] visited = new boolean[s.length()+1]; visited[0]=true; while(!queue.isEmpty()){ int size = queue.size(); while(size-->0){ int start = queue.poll(); if(start>=s.length()) return level-1; // Level signifies the minimum partitions required to create a palindromic partition. Now, if partition is k, then cuts will be k-1. for(int end = start; end0 partitions, so, `dp[n][k>0] = INF`. Also, If we have an non-empty string then that string can't be partitioned in k=0 palindromic substrings, so, `dp[i 2, if edge characters s[i] and s[j] are same then modification required = palindromeDp[i+1][j-1], else modification required = palindromeDp[i+1][j-1] + 1. So, we will take the string s on both x & y axis of the integer array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java // Top down recursive class Solution { public int palindromePartition(String s, int k) { int[][] dp = new int[s.length()][k+1]; for (int[] i : dp) Arrays.fill(i, -1); int[][] palindromeDp = new int[s.length()][s.length()]; // Here we need to populate the changesDP because because of the k value, all the recursions are not getting executed and thus value of palindromeDp[i+1][j-1] is not available while calculating palindromeDp[i][j]. for(int gap=0;gap= s.length() && k == 0) return 0; if (start >= s.length() || k <= 0) return Integer.MAX_VALUE; if (dp[start][k] != -1) return dp[start][k]; int min = Integer.MAX_VALUE; for (int end = start; end < s.length(); end++) { int changesRequired = palindromeDp[start][end]; int x = dfsDp(s, end + 1, k - 1, dp, palindromeDp); if (x == Integer.MAX_VALUE) continue; min = Math.min(min, x + changesRequired); } return dp[start][k] = min; } } ``` ### Buttom Up Iterative Approach: Here we will be using buttom up dp. As we can see, the solution depends on two factors, one being the string and the other being the k value. Based on the k value, the minimum number of characters that requires modification for any input string varies. So, we will be creating a 2d integer dp array, where one dimension would be the input string index and other being the k value. So, dp[index][k] stores the minimum number of modification required so that the string s[index:n] can be converted to k palindromic substrings. We can partition an empty string into k=0 partitions with 0 modifications. So, `dp[n][0] = 0`. But we can't partition an empty string into k>0 partitions, so, `dp[n][k>0] = INF`. Also, If we have an non-empty string then that string can't be partitioned in k=0 palindromic substrings, so, `dp[i= 0; startIndex--) { for (int kValue = 0; kValue <= k; kValue++) { if (startIndex == s.length() && kValue == 0) dp[startIndex][kValue] = 0; else if (startIndex == s.length() || kValue == 0) dp[startIndex][kValue] = Integer.MAX_VALUE; else { int min = Integer.MAX_VALUE; for (int endIndex = startIndex; endIndex < s.length(); endIndex++) { if (dp[endIndex + 1][kValue - 1] != Integer.MAX_VALUE) { min = Math.min(min, palindromeDp[startIndex][endIndex] + dp[endIndex + 1][kValue - 1]); } } dp[startIndex][kValue] = min; } } } return dp[0][k]; } } ``` ## LC 1745. Palindrome Partitioning IV Given a string `s`, return `true` if it is possible to split the string `s` into `three` non-empty palindromic substrings. Otherwise, return `false`. A string is said to be palindrome if it the same string when reversed. ### Top down DP approach: The problem asks us to return `true` if its possible to partition the string into 3 palindromic substrings. But for the purpose of generality, Lets modify the problem as: Return true if its possible to split the string into k palindromic substrings. And then solve it for k=3. We can use dp to solve this problem. The solution depends on two factors, one being the string and the other being the k value. Whether its possible to partition the string into k plaindromic substrings depends on the value of k. We will be usign 2d boolean array as the dp array, where one dimension would be the input string index and other being the k value. So, dp[index][k] stores whether its possible to partition string s[index:n] into k palindromic substrings. We can always partition an empty string(i.e. index=n) into k=0 partitions. So, `dp[n][0] = true`. But we can't partition a empty string(i.e. index=n) into k>0 partitions. So, `dp[n][k>0] = false`. Also, we can't partition a non-empty string(i.e. `index 2, if edge characters s[i] and s[j] are same then modification required = palindromeDp[i+1][j-1], else modification required = palindromeDp[i+1][j-1] + 1. So, we will take the string s on both x & y axis of the integer array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java class Solution1 { public boolean checkPartitioning(String s) { int k =3; Boolean[][] dp = new Boolean[s.length()][k+1]; boolean[][] palindromeDp = new boolean[s.length()][s.length()]; for(int gap=0;gap=s.length() && k==0) return true; if(start>=s.length() || k==0) return false; if(dp[start][k]!=null) return dp[start][k]; for(int end =start; end0 partitions. So, `dp[n][k>0] = false`. Also, we can't partition a non-empty string(i.e. `index= 0; startIndex--) { for (int kValue = 0; kValue <= k; kValue++) { if (startIndex == s.length() && kValue == 0) dp[startIndex][kValue] = true; else if (startIndex == s.length() || kValue == 0) dp[startIndex][kValue] = false; else { for (int endIndex = startIndex; endIndex < s.length(); endIndex++) { if (palindromeDp[startIndex][endIndex] && dp[endIndex + 1][kValue - 1]) { dp[startIndex][kValue] = true; } } } } } return dp[0][k]; } } ``` ### Approach: By Diving the string into 3 parts and using palindrome DP: The idea is to break the string into three parts. We will have two indexes, i & j, so the 3 strings will be s[0:i], s[i:j] and s[j:n]. We initially start from i=1 and go till n-2. And for each i value, j varies from i+1 to n-1. Now for each such combination of i & j, we need to check if all the three strings s[0:i], s[i:j] and s[j:n] are palindrome. If all three string are palindrome, then return true. If we are unable to find any combination of s[0:i], s[i:j] and s[j:n], such that all are palindrome, then return false. Now, for checking if a string s[start:end] is a palindrome, we use a pre-computed palindrome dp array to store the result of isPalindrome(start, end) for all possible combination pair of start & end. **Pre-calculating the palindrome dp:** We can use a 2d integer dp array to store the number of modification required to convert the string from start_index to end_index into a palindrome for every possible value of start and end index. For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome. Strings of length 1 are always palindrome, so modification required is zero. Strings of length 2 are palindrome only if the edge characters are same. So, if edges match modification required is `0` else `1`. And for length > 2, if edge characters s[i] and s[j] are same then modification required = palindromeDp[i+1][j-1], else modification required = palindromeDp[i+1][j-1] + 1. So, we will take the string s on both x & y axis of the integer array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. ```java class Solution { public boolean checkPartitioning(String s) { boolean[][] palindrome = new boolean[s.length()][s.length()]; for (int gap = 0; gap < s.length(); gap++) { for (int i = 0, j = gap; j < s.length(); i++, j++) { if (gap == 0) palindrome[i][j] = true; else if (gap == 1) palindrome[i][j] = s.charAt(i) == s.charAt(j); else palindrome[i][j] = s.charAt(i) == s.charAt(j) && palindrome[i + 1][j - 1]; } } for (int i = 1; i < s.length() - 1; i++) { for (int j = i + 1; j < s.length(); j++) { if (palindrome[0][i - 1] && palindrome[i][j - 1] && palindrome[j][s.length() - 1]) return true; } } return false; } } ``` ## LC 647. Palindromic Substrings Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string. For s = "abc", Three palindromic strings: "a", "b", "c". For s = "aaa", Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". ### Using palindrome DP approach: We will be using dp to solve this. We will be using a 2D boolean array to store whether a substring from index i to j is a palindrome or not. The palindrome[i][j] value will be true if the substring from i to j is a palindrome; otherwise, it will be false. For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome. Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j ]should be same and palindrome[i+1][j-1] should be true. So, we will take the string s on both x & y axis of the boolean array.We will traverse the dp array diagonally. Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1. The code uses two nested loops to traverse through all possible substrings of the input string s. The outer loop (gap) represents the length of the substring, and the inner loop iterates through the possible starting indices of the substring. For each gap length and starting index i, the ending index j is calculated as i + gap. If the gap is 1, then the substring has a length of 2, and the palindrome[i][j] value is set to true if the characters at i and j are the same (i.e., a palindrome of length 2). For gap greater than 1, the code checks if the characters at i and j are the same. If they are, it also checks if the substring from i+1 to j-1 is a palindrome, which is stored in palindrome[i+1][j-1]. If both conditions are true, then the substring from i to j is a palindrome, and palindrome[i][j] is set to true. Whenever the palindrome[i][j] value is found to be true, it means the substring from i to j is a palindrome, and the count is increased by 1. The final count gives the total number of palindromic substrings present in the given string s. ```java class Solution { public int countSubstrings(String s) { boolean[][] palindrome = new boolean[s.length()][s.length()]; int count = 0; for(int gap=0;gap(e+1)/2).sum(); } private int[] manachersAlgorithm(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { sb.append('#').append(c); } sb.append('#'); sb.insert(0, '$').append('^'); char[] chars = sb.toString().toCharArray(); int n = chars.length - 2; int[] manacher = new int[chars.length]; int left = 0, right = 0; for (int i = 1; i <= n; i++) { if (i > right) { while (chars[i - manacher[i] - 1] == chars[i + manacher[i] + 1]) { manacher[i]++; } left = i - manacher[i]; right = i + manacher[i]; } else { int mirrorIndex = left + right - i; if (mirrorIndex - manacher[mirrorIndex] < left) { // When mirrorIndex have palindrome whose length exceeds the left boundary, we only consider the length till the left boundary. manacher[i] = right - i; } else { manacher[i] = manacher[mirrorIndex]; // Else consider the whole palindrome length as initial value. } while (chars[i - manacher[i] - 1] == chars[i + manacher[i] + 1]) { manacher[i]++; } if (i + manacher[i] > right) { left = i - manacher[i]; right = i + manacher[i]; } } } return Arrays.stream(manacher, 1, n + 1).toArray(); } } ``` ## LC 2484. Count Palindromic Subsequences Given a string of digits `s`, return the number of palindromic subsequences of `s` having length `5`. Since the answer may be very large, return it modulo `10^9 + 7`. **Note:** - A string is palindromic if it reads the same forward and backward. - A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. ### Dynamic Programming Approach: We will be using dp to solve this problem. `dp[index][patternIndex]` stores the number of palindromes that can be formed using the `pattern[patternIndex:patternEnd]` when matched with `s[index:sEnd]`. Since, the input string only contains digits and we need to find palindromic subsequences of length `5`, which is a odd length palindrome, we can form all possible subsequence patterns with wildcard `*` in the middle and 2 digits on the left and 2 digits on the right. We iterates over all possible pairs of characters from `'0'` to `'9'`, representing the first 2 characters and last 2 characters of the palindrome. For each pair, it constructs a pattern string by concatenating the first character, the second character, a wildcard character `('*')`, the second character again, and the first character again. i.e. `C1C2*C2C1`. For each such subsequence wildcard pattern, `p`, we initialize the 2d dp with `-1`. And we call a recursive dp method which returns the numbers of palindromic subsequences that can be formed by the input string `s`, when matched with subsequence wildcard pattern, `p`. We call the recursive dp method for all possible subsequence wildcard patterns and add up the counts from each one of them. In the recursive dp method, If the wildcard pattern has reached the end of the pattern, i.e `patternIndex >= patternEnd`, then return `1`. Else if we have reached to the end of the input string but the pattern index has not reached the end of the pattern, i.e. `index>=sEnd && patternIndex= s.length()) { return patternIndex == pattern.length() ? 1 : 0; } if (dp[index][patternIndex] != -1) return dp[index][patternIndex]; dp[index][patternIndex] = doDp(index + 1, patternIndex, pattern, s, dp); // Not selecting current index. if (pattern.charAt(patternIndex) == '*' || pattern.charAt(patternIndex) == s.charAt(index)) { dp[index][patternIndex] = (dp[index][patternIndex] + doDp(index + 1, patternIndex + 1, pattern, s, dp)) % MOD; } return dp[index][patternIndex]; } } ``` ### Approach: By Counting Prefix & Suffix: We will be using `3d` prefix and suffix array. `prefix[index][c1][c2]` stores the count of occurences of the subsequence character pair `c1c2` in the string `s[0:index]`. `suffix[index][c1][c2]` stores the count of occurences of the subsequence character pair `c2c1` in the string `s[index:n]`. Since c1 & c2 can range from `'0'` to `'9'`,i.e. 10 characters, `prefix = new int[n][10][10]` and `suffix = new int[n][10][10]`. We will be also maintaining a count variable, where count[i] stores the occurences of the digit `i` in the string s[0:i] when parsing the string from the start and it stores the occurences of the digit `i` in the string s[i:n] when parsing the string from the end. First, we will be iterating over the characters in the input string s from left to right. For each character, the loop first calculates the value of currentChar by subtracting the ASCII value of ‘0’ from the ASCII value of the current character. This converts the character to its corresponding integer value. If the current index is greater than 0, meaning that it is not the first character in the string, the loop then enters two nested for loops that iterate over all possible pairs of characters (represented by c1 and c2). For each pair of characters, the loop updates the prefix array by setting its value at the current index, c1, and c2 to be equal to its value at the previous index, c1, and c2. i.e. `prefix[index][c1][c2] = prefix[index - 1][c1][c2]`. If c2 is equal to currentChar, then there can be count[c1] newly discovered pairs of c1c2. Because every c1 can be paired with current c2. We will increment the value of prefix at the current index, c1, and c2 by the value of count[c1]. After updating the prefix array, we increment the value of count[currentChar] by 1. This keeps track of the number of occurrences of each character in the string. Then, we will be iterating over the characters in the input string from right to left. For each character, it calculates the value of currentChar in the same way as before. If the current index is less than n-1, meaning that it is not the last character in the string, it enters two nested for loops that iterate over all possible pairs of characters. For each pair of characters, it updates the suffix array by setting its value at the current index, c1, and c2 to be equal to its value at the next index, c1, and c2. i.e. `suffix[index][c1][c2] = suffix[index + 1][c1][c2]`. If c2 is equal to currentChar, then there can be count[c1] newly discovered pairs of c1c2. Because every c1 can be paired with current c2. We will increment the value of suffix at the current index, c1, and c2 by the value of count[c1]. After updating the suffix array, we increment the value of count[currentChar] by 1. This keeps track of the number of occurrences of each character in the string. Since, we need to find palindromes of length 5. And if `i` is the middle character then there should be atleast 2 characters on the left of `i` and 2 characters on the right of `i`. We will start iterating from i=2 to n-3, so that atleast s[0] and s[1] can form a pair on the left of i. And s[n-1] and s[n-2] can form a pair on the right of i. Now, for each i, the number of palindromes that can form while keeping the s[i] as the middle element, can be given by the number of occurence of the pair c1c2 until index-1 on the left multiplied by the number of occurence of the pair c2c1 until index+1 on the right for all possible values of c1c2. i.e. `prefix[index - 1][c1][c2] * suffix[index + 1][c1][c2]` for all possible combination of c1 and c2. For i=2 to n-3, for all possible pairs c1c2, we add up the multiplied values of `prefix[index - 1][c1][c2] * suffix[index + 1][c1][c2]` into a variable. And return this variable as the final answer. **Time Complexity:** The time complexity of this algorithm is `O(n)`, where `n` is the length of the input string `s`. The first two for loops each have a time complexity of `O(n)`, since they iterate over the characters in the input string once. The nested for loops inside these loops have a constant time complexity of `O(1)`, since they iterate over all possible pairs of characters, and there are a constant number of such pairs (100 in this case, since there are 10 possible characters). The third set of nested for loops has a time complexity of O(n), since it iterates over all indices from 2 to n-3. The nested for loops inside this loop also have a constant time complexity of O(1), for the same reason as before. Therefore, the overall time complexity of the algorithm is `O(n) + O(n) + O(n) = O(n)`. ```java class Solution2 { public int countPalindromes(String s) { int mod = 1000_000_007; int n = s.length(); int ans = 0; int[] count = new int[10]; int[][][] prefix = new int[n][10][10]; int[][][] suffix = new int[n][10][10]; for (int index = 0; index < n; index++) { int currentChar = s.charAt(index) - '0'; if (index > 0) for (int c1 = 0; c1 < 10; c1++) for (int c2 = 0; c2 < 10; c2++) { prefix[index][c1][c2] = prefix[index - 1][c1][c2]; if (c2 == currentChar) prefix[index][c1][c2] += count[c1]; } count[currentChar]++; } Arrays.fill(count, 0); for (int index = n - 1; index >= 0; index--) { int currentChar = s.charAt(index) - '0'; if (index < n - 1) for (int c1 = 0; c1 < 10; c1++) for (int c2 = 0; c2 < 10; c2++) { suffix[index][c1][c2] = suffix[index + 1][c1][c2]; if (c2 == currentChar) suffix[index][c1][c2] += count[c1]; } count[currentChar]++; } for (int index = 2; index < n - 2; index++) for (int c1 = 0; c1 < 10; c1++) for (int c2 = 0; c2 < 10; c2++) ans = (int)((ans + (long) prefix[index - 1][c1][c2] * suffix[index + 1][c1][c2]) % mod); return ans; } } ``` ## LC 1147. Longest Chunked Palindrome Decomposition You are given a string `text`. You should split it to `k` substrings (subtext1, subtext2, ..., subtextk) such that: - subtexti is a non-empty string. - The concatenation of all the substrings is equal to `text` (i.e., subtext1 + subtext2 + ... + subtextk == text). - subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k). Return the largest possible value of k. ### Greedy Approach: Two Pointer with Rolling hash. Integer representation of characters: ``` a -> 0 b -> 1 ... z -> 25 ``` Given a string, its rolling hash is calculated from right to left. ``` For example: `"abc"` -> Hash for `c` will be calculated first, then for b, and then for a. hash("abc") = (0 x 26^2) + (1 x 26^1) + (2 x 26^0), which is of the form (character x base ^ power). base = 26, because of there are 26 letters. character = Integer representation of character. power = Index of the character from right. ``` Now, since this value can grow really large and overflow, we need to mod it with some large prime number. **Coming to the problem:** While iterating the string from the end, i.e `right->left`, we can easily calculate the rolling hash in each iteration because the hash is calculate from `right->left`. But while iterating the string from front, i,e left to right, we can't use the same technique because here we are getting the characters from left to right of original string but the hash calculating technique require us to have it in right to left order. So, while iterating from front, we will multiply the previous hash with base, i.e. `26`, then add the character integer to it and mod the whole value. By multiplying the previous hash by base we are shifting the previous base to the left. i.e. We are increasing all previous powers by 1. ``` Example: Say we have "ghi". And we iterate over it. for 'g': hash = ( 6 x 26^0) for 'h': we first multiply the previous hash by base, then previous hash = ( 6 x 26^1), then add ( 7 x 26^0) for 'i': multiply previous hash by base: (6 x 26^2) + (7 x 26^1), then add ( 8 x 26^0). so, Hash becomes: (6 x 26^2) + (7 x 26^1) + ( 8 x 26^0) As, we can see, by multiplying by base everytime we are increasing every previous power by 1, giving us a right to left hash calculation effect. ``` **Here's how the algorithm works:** We use two pointers, starting from extreme left and extreme right. And in each iteration we move them closer, and calculate rolling hash. And once the hash matches, then these two substrings matches. so we increment our count by 2. And reset the rolling hashes, power which depends on the index of substring. And keep running the loop until the pointes are at the same index. Once the loop ends, there can be a 1 length or more substring that doesn't have a mirror string. We check that by `startHash != 0 || endHash != 0 || start == end`. If the startHash or the endHash is non-zero, then there exists a string of `length >=2`, whose palindrome doesn't exist. And if `start == end`, then there exist a string of length `1`. In either of the cases we add `1` to the final answer. To be theoritically correct, once hash matches we should compare the two strings character by character. But with some large prime number and tiny error percentage we can skip that. **Time Complexity:** - Time Complexity Without String Compare: `O(n)` - Time Complexity With String Compare: `O(n^2)` - Space Complexity Without String Compare: `O(1)` - Space Complexity With String Compare: `O(n)`, to store the substrings that needed to be compared. ### DP Approach with Rolling Hash: TODO. ## LC 97. Interleaving String Given 3 strings `string1`, `string2`, and `string3`, find whether `string3` is formed by an interleaving of `string1` and `string2`. An interleaving of two strings `s` and `t` is a configuration where `s` and `t` are divided into `n` and `m` substrings respectively, such that: - `s = s1 + s2 + ... + sn` - `t = t1 + t2 + ... + tm` - `|n - m| <= 1` The interleaving is `s1 + t1 + s2 + t2 + s3 + t3 + ...` or `t1 + s1 + t2 + s2 + t3 + s3 + ...` **Note:** a + b is the concatenation of strings a and b. ### Top Down Recursive DP: We will be using dp to solve this problem. We will be using s1 for string1, s2 for string2 and s3 for string3 from now onwards. i1 will denote current index of s1, i2 will denote current index of s2 and i1+i2 will denote current index of s3, since n1+n2 == n3. We will be using a 2d boolean array as the dp array. dp[i1][i2] stores `true` if its possible to form the input string s3[i1+i2 : n3] by an interleaving of input string s1[i1:n1] and s2[i2:n2], where n1, n2 and n3 represents length of s1, s2 and s3 respectively. s3 can only be formed by interleaving of s1 and s2, iff `n1+n2==n3`. If this condition is false, return false. **Base Case:** When `i1==n1` and `i2==n2`, i.e. both i1 and i2 reached the end of its respective strings and hence both strings are empty, and since we have already verified that `n1+n2==n3`, then the 3rd string is also empty. Two empty strings can always be interleaved into a empty string, so, `dp[n1][n2]=true`. If i1 has not reached end of s1, i.e. `i1= 0; i1--) { for (int i2 = s2.length(); i2 >= 0; i2--) { if (i1 == s1.length() && i2 == s2.length()) dp[i1][i2] = true; else if (i1 == s1.length()) { dp[i1][i2] = dp[i1][i2 + 1] && s3.charAt(i1 + i2) == s2.charAt(i2); } else if (i2 == s2.length()) { dp[i1][i2] = dp[i1 + 1][i2] && s3.charAt(i1 + i2) == s1.charAt(i1); } else { dp[i1][i2] = (dp[i1][i2 + 1] && s3.charAt(i1 + i2) == s2.charAt(i2)) || (dp[i1 + 1][i2] && s3.charAt(i1 + i2) == s1.charAt(i1)); } } } return dp[0][0]; } } ``` ## LC 115. Distinct Subsequences Given two strings `s` and `t`, return the number of distinct subsequences of `s` which equals `t`. The test cases are generated so that the answer fits on a 32-bit signed integer. ### Top Down Recursive DP: We will be using dp to solve this problem. We will be using a 2d integer `dp`, where `dp[sIndex][tIndex]` denotes the number of distinct subsequences of the string `s[sIndex:sEnd]` that is equal to the string `t[tIndex:tEnd]`. Based on the definition of `dp[sIndex][tIndex]`, we can see the smaller problem is on the right and the bigger problem is on the left. So, the base cases will be on the right. If `tIndex>=tEnd`,i.e. we have reached the end of string t, so, now `t[tIndex:tEnd]` represents an empty string. There's only one unique way to form an empty string using `s[sIndex:sEnd]`, by not selecting any character from `s[sIndex:sEnd]`. So, `dp[sIndex][tEnd] = 1`. In other words, With empty target pattern we can form only 1 subsequence where we take no elements from s. If `sIndex>=sEnd and tIndex=t.length()) return 1; if (sIndex >= s.length()) return 0; if (dp[sIndex][tIndex] != -1) return dp[sIndex][tIndex]; int count = 0; count += doDp(t,s,sIndex+1,tIndex, dp); //Ignoring current s character if(s.charAt(sIndex)==t.charAt(tIndex)) count+= doDp(t,s,sIndex+1,tIndex+1, dp); // Considering current s character only when s character is equal to t character. return dp[sIndex][tIndex] = count; } } ``` ### Buttom Up Iterative DP: The approach is very similar to recursive dp approach. We will be using a 2d integer `dp`, where `dp[sIndex][tIndex]` denotes the number of distinct subsequences of the string `s[sIndex:sEnd]` that is equal to the string `t[tIndex:tEnd]`. Based on the definition of `dp[sIndex][tIndex]`, we can see the smaller problem is on the right and the bigger problem is on the left. So, the base cases will be on the right. So, we will run two for loops one for string `s` and other for string `t`, Both the loops will iterate from right to left. So, sIndex will iterate from [sEnd to 0] and tIndex will iterate from [tEnd to 0]. If `tIndex==tEnd`,i.e. we are at the end of string t, so, now `t[tIndex:tEnd]` represents an empty string. There's only one unique way to form an empty string using `s[sIndex:sEnd]`, by not selecting any character from `s[sIndex:sEnd]`. So, `dp[sIndex][tEnd] = 1`. In other words, With empty target string `t` we can form only `1` subsequence where we take no elements from `s`. If `sIndex==sEnd and tIndex= 0; sIndex--) { for (int tIndex = t.length(); tIndex >= 0; tIndex--) { if (tIndex == t.length()) dp[sIndex][tIndex] = 1; // With Empty target pattern we can form only 1 subsequence where we take no elements from s. else if (sIndex == s.length()) dp[sIndex][tIndex] = 0; // With empty string, we cannot form any pattern so 0. else { dp[sIndex][tIndex] = dp[sIndex + 1][tIndex]; // Not selecting current s[col]. if (s.charAt(sIndex) == t.charAt(tIndex)) dp[sIndex][tIndex] += dp[sIndex + 1][tIndex + 1]; // Selecting current s[col] when s[tIndex]==t[sIndex]. } } } return dp[0][0]; } } ``` ## LC 940. Distinct Subsequences II Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo `10^9 + 7`. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not.) ### Dp Approach with deletion of duplicate subsequences from the previous occurence of current character: ``` For the string S = "abab": dp[0] = 1, as it counts (""). dp[1] = 2, as it counts ("", "a"). dp[2] = 4, as it counts ("", "a", "b", "ab"). dp[3] = 7, as it counts ("", "a", "b", "aa", "ab", "ba", "aba"). dp[4] = 12, as it counts ("", "a", "b", "aa", "ab", "ba", "bb", "aab", "aba", "abb", "bab", "abab"). ``` Here, dp[i] represents the count of possible distinct subsequences at index i. At each index i, the subsequences formed include the subsequences at index i-1 once without appending s[i] and once with appending s[i]. If we don't care about removal of duplicate subsequences, then dp[i] = 2 * dp[i-1]. However, in this case, we need to eliminate the duplicate subsequences. Here's the idea: Let's assume we have a character c present at two indices, i and j, where j is greater than i. At index i, the subsequences are obtained by taking the subsequences at index i-1 and duplicating them twice: once without appending the character c, and once with appending the character c at the end. Similarly, at index j, the subsequences consist of the subsequences at index j-1 duplicated twice: once with the character c appended, and once without the character c. Therefore, the subsequences at index j also include the subsequences at index i-1 (when no character is appended to the subsequences at index i-1). Now, since the character at index i and index j is the same, and the subsequences of i-1 are appended by the character c both at index i and index j, this creates duplicate subsequences. To remove the duplicates, we can subtract the subsequences of i-1 from the subsequences of j, obtaining the unique subsequences. For each character, we will keep track of the last index where we encountered the same character before. This index corresponds to i in the above description. Thus, to calculate dp[i], we use the formula: dp[i] = 2 * dp[i-1] - dp[last[c]-1]. To remove the empty subsequence, we subtract 1 from dp[n], i.e., dp[n]--. Finally, if dp[n] is negative due to the deletions, we add the modulo value to make it positive. ```java class Solution { public int distinctSubseqII(String s) { int mod = 1000000007; char[] ch = s.toCharArray(); int[] dp = new int[ch.length+1]; dp[0] = 1; // Emmpty character can form only empty subsequence. int[] last = new int[26]; Arrays.fill(last, -1); for(int i=1;i<=ch.length;i++){ dp[i] = (dp[i-1] * 2)%mod; int c = ch[i-1]-'a'; if(last[c]>=0){ dp[i] = (dp[i]-dp[last[c]-1])%mod; } last[c] = i; } dp[ch.length] -=1; // remove empty subsequence. return dp[ch.length]<0?dp[ch.length]+mod:dp[ch.length]; } } ``` ## LC 443. String Compression Given an array of characters `chars`, compress it using the following algorithm: Begin with an empty string s. For each group of **consecutive repeating characters** in `chars`: - If the group's length is 1, append the character to s. - Otherwise, append the character followed by the group's length. The compressed string `s` **should not be returned separately**, but instead, be stored **in the input character array** `chars`. Note that group lengths that are `10` or longer will be split into multiple characters in `chars`. After you are done **modifying the input array**, return the new length of the array. You must write an algorithm that uses only constant extra space. ### Approach: Iterate the string and when consecutive characters are same, store its count along with the char in the answer. We need to compress the input string such that when consecutive characters are same, they forms a group, then we should replace the group with a single occurence of the character followed by the length of the group. But if the group's length is 1, just append the character. We will be using a while loop iterating from left to right, and inside the for loop we will maintain a integer variable, count, to store the group length. Inside the outer while loop we will be running another while loop that will keep on incrementing the index and the count while s[index+1]==s[index]. We will be using another pointer, resultIndex, keeping track of the next index in `chars` where the next compressed string will be put in. i.e. resultIndex pointer is used to keep track of the position in the compressed array. And, once the inside for loop terminates. if the count is greater than 1 then we append the character followed by count in the compressed array, else if count==1, just append the character in the compressed string. ```java class Solution { public int compress(char[] chars) { int index = 0; int resultIndex = 0; while (index < chars.length) { int count = 1; while (index + 1 < chars.length && chars[index + 1] == chars[index]) { count++; index++; } if (count > 1) { chars[resultIndex++] = chars[index]; for (char c : String.valueOf(count).toCharArray()) chars[resultIndex++] = c; } else { chars[resultIndex++] = chars[index]; } index++; } return resultIndex; } ``` ## LC 1531. String Compression II **Run-length encoding** is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string `"aabccc"` we replace `"aa"` by `"a2"` and replace `"ccc"` by `"c3"`. Thus the compressed string becomes `"a2bc3"`. Notice that in this problem, we are not adding `'1'` after single characters. Given a string `s` and an integer `k`. You need to delete at most `k` characters from `s` such that the run-length encoded version of `s` has minimum length. Find the minimum length of the run-length encoded version of `s` after deleting at most `k` characters. ### Top Down DP Approach using 2D DP: We will be using dp to solve this problem. We will be using a 2d integer dp array where dp[index][k] represents the minimum length of the compressed string that can be obtained by removing at most k characters from the substring of s[index:n]. Initially, we will call the recursive dp method, with index=0 and k=initial_K_Value. With each recursive call index will increase but kValue will decrease. As, we can see the larger problem is on the top-right(when index=0 and k=initial_K_Value) whereas the smaller problem(index=n, k=0) is on the buttom-left. Base cases will be on the buttom-left. If `k<0` , i.e. k is negative, it means that more than k characters have been removed from the string, which is not allowed according to the problem statement. The problem asks to find the minimum length of the compressed string that can be obtained by removing at most k characters from the original string s. So, if k becomes negative during the recursive calls, it means that an invalid solution has been reached where more than k characters have been removed. In this case, we will returns a infinite value (here, Integer.MAX_VALUE/2) to indicate that this is an invalid solution and should not be considered when calculating the minimum length of the compressed string. If the current index is greater than or equal to the length of the string(empty string), or if the remaining length of the string is less than or equal to k (i.e. current kValue is greater or equal to remaining substring of s), it returns 0 to indicate that the remaining string can be compressed to an empty string by removing all remaining characters. If the value of dp[index][k] is not -1, it means that this subproblem has already been solved and its result is stored in the dp array. In this case, the return returns the stored result. We will initialize a variable `res` to store the minimum length of the compressed string for the current value of `index` and `k`. And an array `count` of size 26 to count the occurrences of each character in the current group. Then for starting index, `index`, we will iterate over all possible ending indices `endIndex` for the current group `(from index to n-1)` and keeps track of the maximum count of any character in this range (`maxCount`). The number of characters that need to be removed from this group is `(endIndex - index + 1 - maxCount)`. Then we will recursively call this dp method with the next index (endIndex+1) and an updated value of `k` (decreased by the number of characters removed from this group) to find the minimum length of the compressed string for the remaining substring. The length of the compressed string for this group is calculated as `1 + numberOfDigits(maxCount)` (where `numberOfDigits(maxCount)` returns the number of digits in `maxCount`) and added to the result of the recursive call. The minimum value over all possible groups is stored in `res`. The `1` is added to `numberOfDigits(maxCount)` to account for the length of the character that is being repeated in the current group. The `numberOfDigits(maxCount)` function returns the number of digits in `maxCount`, which represents the number of times the character is repeated. So, `1 + numberOfDigits(maxCount)` gives the total length of the compressed representation of this group, which consists of the character itself (length 1) followed by its count (`length numberOfDigits(maxCount)`). For example, if the current group consists of `3` occurrences of the character `'a'`, then `maxCount` would be 3, `numberOfDigits(maxCount)` would be 1 (since 3 has 1 digit), and 1 + numberOfDigits(maxCount) would be `2`, representing the compressed string `"a3"`. Finally, we will store the result in dp[index][k] and return it. ```java class Solution { // Helper function to calculate the number of digits in x, except when x is 1, in which case it returns 0 private int numberOfDigits(int x) { return x == 1 ? 0 : x < 10 ? 1 : x < 100 ? 2 : 3; } public int getLengthOfOptimalCompression(String s, int k) { // Initialize a 2D array dp of size s.length() by s.length() and fill it with -1 int[][] dp = new int[s.length()][s.length()]; for (int[] arr : dp) Arrays.fill(arr, -1); // Call the doDp method with the starting index 0, the given value of k, the string s, and the dp array return doDp(0, k, s, dp); } // Recursive function that takes as input the current index, the remaining number of characters that can be removed (k), the string s, and the dp array private int doDp(int index, int k, String s, int[][] dp) { // If k is negative, return a large value to indicate that this is an invalid solution if (k < 0) return Integer.MAX_VALUE/2; // If the current index is greater than or equal to the length of the string, // or if the remaining length of the string is less than or equal to k, // return 0 to indicate that the remaining string can be compressed to an empty string by removing all remaining characters if (index >= s.length() || s.length() - index <= k) return 0; // If the value of dp[index][k] is not -1, it means that this subproblem has already been solved and its result is stored in the dp array if (dp[index][k] != -1) return dp[index][k]; // Initialize a variable res to store the minimum length of the compressed string int res = Integer.MAX_VALUE/2; // Initialize an array count of size 26 to count the occurrences of each character in the current group int[] count = new int[26]; // Iterate over all possible ending indices endIndex for the current group (from index to s.length()-1) for (int endIndex = index, maxCount = 0; endIndex < s.length(); endIndex++) { // Keep track of the maximum count of any character in this range (maxCount) maxCount = Math.max(maxCount, ++count[s.charAt(endIndex) - 'a']); // The number of characters that need to be removed from this group is (endIndex - index + 1 - maxCount) // Call itself recursively with the next index (endIndex+1) and an updated value of k (decreased by the number of characters removed from this group) // to find the minimum length of the compressed string for the remaining substring res = Math.min(res, 1 + numberOfDigits(maxCount) + doDp(endIndex + 1, k - (endIndex - index + 1 - maxCount), s, dp)); } // Store the result in dp[index][k] and return it return dp[index][k] = res; } } ``` ## LC 472. Concatenated Words Given an array of strings `words` **(without duplicates)**, return all the **concatenated words** in the given list of words. A **concatenated word** is defined as a string that is comprised entirely of at least two shorter words (not necesssarily distinct) in the given array. ### Buttom Up Iterative DP: We will be using bottom-up DP to solve this. We will be using a `1d` boolean DP. `dp[i]` signifies whether it's possible to form the string `s[i:n]` by using the words in the dictionary. Since empty strings can always be formed no matter what words are there in the dictionary, `dp[n] = true`. As we can see, the smaller problem is on the right and the larger problem is on the left. We will be iterating from right to left, and for every index `i`, we will run another loop where `j` ranges from `[i+1 to n]`, such that `s[i:j]` will form all possible substrings starting at `i`. Now, for each such substring, we need to check if the substring is present in the dictionary. If it is present, then we need to solve the subproblem `dp[j]`. This is because we know `s[i:j]` matches a string in the dictionary, and then we need to check if the rest of the string matches words in the dictionary. We can find this information in `dp[j]`. If `dp[j]` returns true, we set `dp[i]` to true. For any given `i`, there should be at least one `j` value such that the substring `s[i:j]` is present in the dictionary and `dp[j]` is true for `dp[i]` to be true. Otherwise, `dp[i]` will be false. Once the loops end, we finally return `dp[0]` as the answer since the larger problem is on the left. Since the larger word that is to be formed and the smaller words that need to be concatenated to form the larger word are both present in the dictionary, we need to remove the larger word from the dictionary before calling the dp. We will iterate over each word in the dictionary, remove it from the dictionary, and then check if the word can be formed by concatenating other words in the dictionary by calling `dp[0]`. If it can, the word is added to the answer list `ans`. The word is then added back to the dictionary. Note that for every word in the dictionary, we are calling the dp method afresh. ```java class Solution { public List findAllConcatenatedWordsInADict(String[] words) { Set dict = new HashSet<>(Arrays.asList(words)); List ans = new ArrayList<>(); for (String word : words) { dict.remove(word); if (doDp(word, dict)) ans.add(word); dict.add(word); } return ans; } private boolean doDp(String word, Set dict) { boolean[] dp = new boolean[word.length() + 1]; dp[word.length()] = true; for (int i = word.length() - 1; i >= 0; i--) { for (int j = i + 1; j <= word.length(); j++) { if (dp[j] && dict.contains(word.substring(i, j))) { dp[i] = true; break; } } } return dp[0]; } } ``` ### DFS Approach: We can use DFS to solve this. Since we need to return `true/false` but not some min/max value, DFS works very well here. We will first create a HashSet, `dict`, of all words in the given list and then iterate through each word in the list. For each word, we will remove it from the dict and check if that word can be formed by concatenating two or more shorter words from the dict using dfs with a `visited` array. If it can be formed, then it is added to the answer list. Finally, the word is added back to the dict. We will call the dfs with four arguments: the current word being checked, `word`, the set of all words in the dictionary, `dict`, the starting index of the current substring being checked, `start`, and a boolean array to keep track of which indices have already been visited, `visited`. Since empty strings can always be formed no matter what words are there in the dictionary, i.e., `if (start == n) return true`. As we can see, the smaller problem is on the right and the larger problem is on the left. For every dfs call, first mark the `start` index as visited. Now for the start index, `start`, we will run a loop where `'end'` ranges from `[start+1 to n]`, such that `s[start:end]` will form all possible substrings starting at `start`. We can skip end indexes that are already visited. Now, for each such substring, we need to check if the substring is present in the dictionary. If it is present, then we need to call the dfs recursively with `start = end`. This is because we know `s[start:end]` matches a string in the dictionary, and then we need to check if the rest of the string matches words in the dictionary. We can find this information by calling `dfs(end)`. If `dfs(end)` returns `true`, we can return `true` for `dfs(end)`. For any given start `index`, there should be at least one end index such that the substring `s[start:end]` is present in the dictionary and `dfs(end)` returns `true` for `dfs(start)` to be `true`. Otherwise, `dfs(start)` will be `false`. Initially, we will call the dfs with `start = 0` and return its result as the answer. ```java class Solution { public List findAllConcatenatedWordsInADict(String[] words) { Set dict = new HashSet<>(Arrays.asList(words)); List ans = new ArrayList<>(); for (String word : words) { dict.remove(word); if (dfs(word, dict, 0, new boolean[word.length()+1])) ans.add(word); dict.add(word); } return ans; } private boolean dfs(String word, Set dict, int start, boolean[] visited) { if (start == word.length()) return true; visited[start]=true; for (int end = start + 1; end <= word.length(); end++) { if (!visited[end] && dict.contains(word.substring(start, end)) && dfs(word, dict, end, visited)) { return true; } } return false; } } ``` ## LC 712. Minimum ASCII Delete Sum for Two Strings Given two strings `s1` and `s2`, return the lowest ASCII sum of deleted characters to make two strings equal. ### Top Down DP: We will use dp to solve this problem. We will be using a 2d integer dp array. dp[s1Index][s2Index] represents the sum of all deleted ASCII characters to match s1[s1Index:n1] and s2[s2Index:n2]. As we can see the smaller problem is on the right buttom and the larger problem is on the top left. The idea is that, we will be using two pointers, s1Index pointing to current index in s1 and s2Index pointing to current index in s2. Initially, we will start s1Index=0 and s2Index=0, i.e from the start of both strings, as the larger problem is on the left. Now, we will be comparing the s1[s1Index] character with s2[s2Index] character. There can be five scenarios based on the comparison: 1. When both s1Index and s2Index has reached the end of s1 and s2 respectively. 2. s1Index has reached the end of s1 but there are characters left in s2. 3. s2Index has reached the end of s2 but there are characters left in s1. 4. The characters match. 5. The characters don't match. Let's talk about all 5 scenarios one by one. **When both s1Index and s2Index has reached the end of s1 and s2 respectively:** If both s1Index and s2Index have reached the end of its corresponding strings,i.e. `s1Index=n1` and `s2Index=n2`, then both s1[s1Index:n1] and s2[s2Index:n2] represents empty string. Since empty strings can be matched without any deletions, dp[n1][n2]=0. **s1Index has reached the end of s1 but there are characters left in s2:** If s1Index has reached the end of s1, then the string s1[s1Index:n1] represents an empty string but s2[s2Index:n2] is a non-empty string. To match a non-empty string with an empty string, we need to remove all the characters from the non-empty string s2[s2Index:n2] to match with s1[s1Index:n1]. There's two ways we can do that. First, by summing up all the ascii values for all the characters in s2[s2Index:n2] and storing it in dp[n1][s2Index]. Second, by calling the subproblem dp[n1][s2Index+1] and then adding ascii value of s2[s2Index] to it and storing the result in dp[n1][s2Index], i.e. we are deleting the s2[s2Index] character and delegating it to the subproblem dp[n1][s2Index+1]. **s2Index has reached the end of s2 but there are characters left in s1:** If s2Index has reached the end of s2, then the string s2[s2Index:n2] represents an empty string but s1[s1Index:n1] is a non-empty string. To match a non-empty string with an empty string, we need to remove all the characters from the non-empty string s1[s1Index:n1] to match with s2[s2Index:n2]. There's two ways we can do that. First, by summing up all the ascii values for all the characters in s1[s1Index:n1] and storing it in dp[s1Index][n2]. Second, by calling the subproblem dp[s1Index+1][n2] and then adding ascii value of s1[s1Index] to it and storing the result in dp[s1Index][n2], i.e. we are deleting the s1[s1Index] character and delegating it to the subproblem dp[s1Index+1][n2]. **When the characters match:** If the character at s1[s1Index] matches with s2[s2Index], then no deletion is required to match the current characters, so, we delegate the problem to dp[s1Index+1][s2Index+1] and store the returned value into dp[s1Index][s2Index]. **When the characters don't match:** When the current characters in s1 and s2 don't match, we need to remove the current character once from s1 and once from s2 and take minimum value of both. If s1[s1Index] is deleted then we call the subproblem dp[s1Index+1][s2Index] and add the adcii value of s1[s1Index] to it. If s2[s2Index] is deleted then we call the subproblem dp[s1Index][s2Index+1] and add the adcii value of s2[s2Index] to it. Finally we take the minimum of the two and store it in dp[s1Index][s2Index]. ```java class Solution1 { // Top Down DP public int minimumDeleteSum(String s1, String s2) { int[][] dp = new int[s1.length() + 1][s2.length() + 1]; // dp[i][j] represents the sum of all deleted characters to match s1[i:](from ith char to end) and s2[j:](from jth char to end). return doDp(0, 0, dp, s1, s2); } private int doDp(int i1, int i2, int[][] dp, String s1, String s2) { if (i1 >= s1.length() && i2 >= s2.length()) return 0; // Since both the index are at the last position, i.e. both are empty strings. And empty strings are always sorted. if (dp[i1][i2] != 0) return dp[i1][i2]; else if (i1 >= s1.length()) return dp[i1][i2] = doDp(i1, i2 + 1, dp, s1, s2) + s2.codePointAt(i2); // If one string is empty, then we need to remove every character from the other string to match them. else if (i2 >= s2.length()) return dp[i1][i2] = doDp(i1 + 1, i2, dp, s1, s2) + s1.codePointAt(i1); if (s1.charAt(i1) == s2.charAt(i2)) { // If characters match, then nothing to delete, so we move to next characters. return dp[i1][i2] = doDp(i1 + 1, i2 + 1, dp, s1, s2); } else { // If chars dont match, try removing char from s1 and s2, which ever gives smaller sum, return that. return dp[i1][i2] = Math.min(doDp(i1, i2 + 1, dp, s1, s2) + s2.codePointAt(i2), doDp(i1 + 1, i2, dp, s1, s2) + s1.codePointAt(i1)); } } } ``` ### Buttom Up Iterative DP: We will use dp to solve this problem. We will be using a 2d integer dp array. dp[s1Index][s2Index] represents the sum of all deleted ASCII characters to match s1[s1Index:n1] and s2[s2Index:n2]. As we can see the smaller problem is on the right buttom and the larger problem is on the top left. The idea is that, we will be using two pointers, s1Index pointing to current index in s1 and s2Index pointing to current index in s2. We will run two for loops one for iterating from right to left using s1Index and another to iterate from right to left using s2Index. Initially, we will start s1Index=n1 and s2Index=n2, i.e from the end of both strings, as the smaller problem is on the right. Now, we will be comparing the s1[s1Index] character with s2[s2Index] character. There can be five scenarios based on the comparison: 1. When both s1Index and s2Index has reached the end of s1 and s2 respectively. 2. s1Index has reached the end of s1 but there are characters left in s2. 3. s2Index has reached the end of s2 but there are characters left in s1. 4. The characters match. 5. The characters don't match. Let's talk about all 5 scenarios one by one. **When both s1Index and s2Index has reached the end of s1 and s2 respectively:** If both s1Index and s2Index are at the end of their corresponding strings,i.e. `s1Index=n1` and `s2Index=n2`, then both s1[s1Index:n1] and s2[s2Index:n2] represents empty string. Since empty strings can be matched without any deletions, dp[n1][n2]=0. **s1Index has reached the end of s1 but there are characters left in s2:** If s1Index has reached the end of s1, then the string s1[s1Index:n1] represents an empty string but s2[s2Index:n2] is a non-empty string. To match a non-empty string with an empty string, we need to remove all the characters from the non-empty string s2[s2Index:n2] to match with s1[s1Index:n1]. There's two ways we can do that. First, by summing up all the ascii values for all the characters in s2[s2Index:n2] and storing it in dp[n1][s2Index]. Second, by calling the subproblem dp[n1][s2Index+1] and then adding ascii value of s2[s2Index] to it and storing the result in dp[n1][s2Index], i.e. we are deleting the s2[s2Index] character and delegating it to the subproblem dp[n1][s2Index+1]. **s2Index has reached the end of s2 but there are characters left in s1:** If s2Index has reached the end of s2, then the string s2[s2Index:n2] represents an empty string but s1[s1Index:n1] is a non-empty string. To match a non-empty string with an empty string, we need to remove all the characters from the non-empty string s1[s1Index:n1] to match with s2[s2Index:n2]. There's two ways we can do that. First, by summing up all the ascii values for all the characters in s1[s1Index:n1] and storing it in dp[s1Index][n2]. Second, by calling the subproblem dp[s1Index+1][n2] and then adding ascii value of s1[s1Index] to it and storing the result in dp[s1Index][n2], i.e. we are deleting the s1[s1Index] character and delegating it to the subproblem dp[s1Index+1][n2]. **When the characters match:** If the character at s1[s1Index] matches with s2[s2Index], then no deletion is required to match the current characters, so, we delegate the problem to dp[s1Index+1][s2Index+1] and store the returned value into dp[s1Index][s2Index]. **When the characters don't match:** When the current characters in s1 and s2 don't match, we need to remove the current character once from s1 and once from s2 and take minimum value of both. If s1[s1Index] is deleted then we call the subproblem dp[s1Index+1][s2Index] and add the adcii value of s1[s1Index] to it. If s2[s2Index] is deleted then we call the subproblem dp[s1Index][s2Index+1] and add the adcii value of s2[s2Index] to it. Finally we take the minimum of the two and store it in dp[s1Index][s2Index]. ```java class Solution{ public int minimumDeleteSum(String s1, String s2) { int n1 = s1.length(), n2 = s2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; dp[n1][n2] = 0; for (int s1Index = n1; s1Index >= 0; s1Index--) { for (int s2Index = n2; s2Index >= 0; s2Index--) { if (s1Index == n1 && s2Index == n2) dp[s1Index][s2Index] = 0; else if (s1Index == n1) dp[s1Index][s2Index] = dp[s1Index][s2Index + 1] + s2.charAt(s2Index); else if (s2Index == n2) dp[s1Index][s2Index] = dp[s1Index + 1][s2Index] + s1.charAt(s1Index); else if (s1.charAt(s1Index) == s2.charAt(s2Index)) dp[s1Index][s2Index] = dp[s1Index + 1][s2Index + 1]; else dp[s1Index][s2Index] = Math.min(dp[s1Index + 1][s2Index] + s1.charAt(s1Index), dp[s1Index][s2Index + 1] + s2.charAt(s2Index)); } } return dp[0][0]; } } ```