Skip to content

2746. Decremental String Concatenation 👍

  • Time: $O(n \cdot 26^2) = O(n)$
  • Space: $O(n \cdot 26^2) = O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minimizeConcatenatedLength(vector<string>& words) {
    // dp[i][first][last] := min concatenated length of first i words starting
    // with `first` and ending with `last`
    dp.resize(words.size(), vector<vector<int>>(26, vector<int>(26)));
    return words[0].length() + minimizeConcatenatedLength(
                                   words, 1, words[0].front(), words[0].back());
  }

 private:
  vector<vector<vector<int>>> dp;

  int minimizeConcatenatedLength(const vector<string>& words, int i, char first,
                                 char last) {
    if (i == words.size())
      return 0;
    if (dp[i][first - 'a'][last - 'a'] > 0)
      return dp[i][first - 'a'][last - 'a'];
    const char nextFirst = words[i].front();
    const char nextLast = words[i].back();
    return dp[i][first - 'a'][last - 'a'] =
               words[i].length() +
               min(
                   // join(words[i - 1], words[i])
                   minimizeConcatenatedLength(words, i + 1, first, nextLast) -
                       (last == nextFirst ? 1 : 0),
                   // join(words[i], words[i - 1])
                   minimizeConcatenatedLength(words, i + 1, nextFirst, last) -
                       (first == nextLast ? 1 : 0));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int minimizeConcatenatedLength(String[] words) {
    dp = new int[words.length][26][26];
    return words[0].length() + minimizeConcatenatedLength(words, 1, words[0].charAt(0),
                                                          words[0].charAt(words[0].length() - 1));
  }

  private int[][][] dp;

  private int minimizeConcatenatedLength(String[] words, int i, char first, char last) {
    if (i == words.length)
      return 0;
    if (dp[i][first - 'a'][last - 'a'] > 0)
      return dp[i][first - 'a'][last - 'a'];
    final char nextFirst = words[i].charAt(0);
    final char nextLast = words[i].charAt(words[i].length() - 1);
    return dp[i][first - 'a'][last - 'a'] =
               words[i].length() +
               Math.min(minimizeConcatenatedLength(words, i + 1, first, nextLast) -
                            (last == nextFirst ? 1 : 0),
                        minimizeConcatenatedLength(words, i + 1, nextFirst, last) -
                            (first == nextLast ? 1 : 0));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minimizeConcatenatedLength(self, words: List[str]) -> int:
    @functools.lru_cache(None)
    def dp(i: int, first: str, last: str) -> int:
      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])