2746. Decremental String Concatenation LeetCode Solution
In this guide, you will get 2746. Decremental String Concatenation LeetCode Solution with the best time and space complexity. The solution to Decremental String Concatenation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Decremental String Concatenation solution in C++
- Decremental String Concatenation solution in Java
- Decremental String Concatenation solution in Python
- Additional Resources
Problem Statement of Decremental String Concatenation
You are given a 0-indexed array words containing n strings.
Let’s define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted.
For example join(“ab”, “ba”) = “aba” and join(“ab”, “cde”) = “abcde”.
You are to perform n – 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n – 1, for the ith operation, you can do one of the following:
Make stri = join(stri – 1, words[i])
Make stri = join(words[i], stri – 1)
Your task is to minimize the length of strn – 1.
Return an integer denoting the minimum possible length of strn – 1.
Example 1:
Input: words = [“aa”,”ab”,”bc”]
Output: 4
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2:
str0 = “aa”
str1 = join(str0, “ab”) = “aab”
str2 = join(str1, “bc”) = “aabc”
It can be shown that the minimum possible length of str2 is 4.
Example 2:
Input: words = [“ab”,”b”]
Output: 2
Explanation: In this example, str0 = “ab”, there are two ways to get str1:
join(str0, “b”) = “ab” or join(“b”, str0) = “bab”.
The first string, “ab”, has the minimum length. Hence, the answer is 2.
Example 3:
Input: words = [“aaa”,”c”,”aba”]
Output: 6
Explanation: In this example, we can perform join operations in the following order to minimize the length of str2:
str0 = “aaa”
str1 = join(str0, “c”) = “aaac”
str2 = join(“aba”, str1) = “abaaac”
It can be shown that the minimum possible length of str2 is 6.
Constraints:
1 <= words.length <= 1000
1 <= words[i].length <= 50
Each character in words[i] is an English lowercase letter
Complexity Analysis
- Time Complexity: O(n \cdot 26^2) = O(n)
- Space Complexity: O(n \cdot 26^2) = O(n)
2746. Decremental String Concatenation LeetCode Solution in C++
class Solution {
public:
int minimizeConcatenatedLength(vector<string>& words) {
vector<vector<vector<int>>> mem(words.size(),
vector<vector<int>>(26, vector<int>(26)));
return words[0].length() + minimizeConcatenatedLength(words, 1,
words[0].front(),
words[0].back(), mem);
}
private:
// Returns the minimum concatenated length of the first i words starting with
// `first` and ending in `last`.
int minimizeConcatenatedLength(const vector<string>& words, int i, char first,
char last, vector<vector<vector<int>>>& mem) {
if (i == words.size())
return 0;
const int j = first - 'a';
const int k = last - 'a';
if (mem[i][j][k] > 0)
return mem[i][j][k];
const char nextFirst = words[i].front();
const char nextLast = words[i].back();
return mem[i][j][k] = //
words[i].length() +
min(
// join(words[i - 1], words[i])
minimizeConcatenatedLength(words, i + 1, first, nextLast, mem) -
(last == nextFirst ? 1 : 0),
// join(words[i], words[i - 1])
minimizeConcatenatedLength(words, i + 1, nextFirst, last, mem) -
(first == nextLast ? 1 : 0));
}
};
/* code provided by PROGIEZ */2746. Decremental String Concatenation LeetCode Solution in Java
class Solution {
public int minimizeConcatenatedLength(String[] words) {
int[][][] mem = new int[words.length][26][26];
return words[0].length() + minimizeConcatenatedLength(words, 1, words[0].charAt(0),
words[0].charAt(words[0].length() - 1),
mem);
}
private int minimizeConcatenatedLength(String[] words, int i, char first, char last,
int[][][] mem) {
if (i == words.length)
return 0;
final int j = first - 'a';
final int k = last - 'a';
if (mem[i][j][k] > 0)
return mem[i][j][k];
final char nextFirst = words[i].charAt(0);
final char nextLast = words[i].charAt(words[i].length() - 1);
return mem[i][j][k] = //
words[i].length() + //
Math.min(
// join(words[i - 1], words[i])
minimizeConcatenatedLength(words, i + 1, first, nextLast, mem) -
(last == nextFirst ? 1 : 0),
// join(words[i], words[i - 1])
minimizeConcatenatedLength(words, i + 1, nextFirst, last, mem) -
(first == nextLast ? 1 : 0));
}
}
// code provided by PROGIEZ2746. Decremental String Concatenation LeetCode Solution in Python
class Solution:
def minimizeConcatenatedLength(self, words: list[str]) -> int:
@functools.lru_cache(None)
def dp(i: int, first: str, last: str) -> int:
"""
Returns the minimum concatenated length of the first i words starting with
`first` and ending in `last`.
"""
if i == len(words):
return 0
nextFirst = words[i][0]
nextLast = words[i][-1]
return len(words[i]) + min(
# join(words[i - 1], words[i])
dp(i + 1, first, nextLast) - (last == nextFirst),
# join(words[i], words[i - 1])
dp(i + 1, nextFirst, last) - (first == nextLast)
)
return len(words[0]) + dp(1, words[0][0], words[0][-1])
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.