We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decremental String Concatenation

Number: 2854

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of strings, you must combine them using a special join operation. The join operation concatenates two strings but, if the last character of the first string equals the first character of the second string, one of the duplicate letters is removed. At every step you can either append the new word to the end of the current string or prepend it to the beginning. Your task is to perform exactly n-1 join operations (where n is the number of words) and determine the minimum possible length of the final string.

Key Insights

  • Only the first and last characters of the current string affect the deletion condition when joining another word.
  • When joining two strings, the extra length added is: len(word) minus 1 if the boundary characters match, otherwise len(word).
  • A dynamic programming (DP) approach can be used where the state is defined by the current string’s first and last characters along with the minimized length.
  • There are only 26 possible characters, so the state space (first and last combinations) is manageable.
  • At each step, evaluate both joining options (append or prepend) and update the minimal length for the resulting (first, last) configuration.

Space and Time Complexity

Time Complexity: O(n * 26 * 26)
Space Complexity: O(26 * 26)
(Note: n is the number of words. The DP state is kept for at most 26*26 combinations per iteration.)

Solution

We solve the problem using dynamic programming. Define a DP state where dp[i][first][last] is the minimum length possible after processing i+1 words, with the resulting string starting with character 'first' and ending with character 'last'. When processing a new word, we consider two join orders:

  1. Append the new word to the end of the current string.
    • If the current string’s last character equals the new word’s first character, we “delete” one of the duplicate characters.
    • New length = current length + len(new word) - (1 if current_last == new_word_first else 0).
    • The resulting string’s first character remains the same; its last character becomes new_word’s last character.
  2. Prepend the new word to the beginning of the current string.
    • If the new word’s last character equals the current string’s first character, we “delete” one of the duplicate characters.
    • New length = len(new word) + current length - (1 if new_word_last == current_first else 0).
    • The resulting string’s first character becomes new_word’s first character; the last character remains unchanged.

We initialize the DP with the first word’s boundaries and length. For each subsequent word, we update the DP for every possible state from the previous iteration. Finally, the answer is the minimal length among all states after processing all words.

Code Solutions

# Python solution with detailed comments

def minConcatenatedLength(words):
    # dp is a dictionary where key is a tuple (first_char, last_char)
    # value is the minimum length achieved with that configuration.
    dp = {}
    first, last = words[0][0], words[0][-1]
    dp[(first, last)] = len(words[0])
    
    # Process each word from index 1 to len(words)-1
    for word in words[1:]:
        next_dp = {}
        word_first, word_last = word[0], word[-1]
        word_len = len(word)
        
        # for each state in dp, perform both join operations.
        for (cur_first, cur_last), cur_length in dp.items():
            # Option 1: Append new word to the right: join(current, word)
            if cur_last == word_first:
                # deletion occurs: remove one char from the new word's contribution.
                new_length = cur_length + word_len - 1
            else:
                new_length = cur_length + word_len
            new_state = (cur_first, word_last)
            # update state if new_length is better
            if new_state not in next_dp or new_length < next_dp[new_state]:
                next_dp[new_state] = new_length

            # Option 2: Prepend new word to the left: join(word, current)
            if word_last == cur_first:
                new_length = cur_length + word_len - 1
            else:
                new_length = cur_length + word_len
            new_state = (word_first, cur_last)
            if new_state not in next_dp or new_length < next_dp[new_state]:
                next_dp[new_state] = new_length
        
        # Update dp dictionary to only the states of the current iteration.
        dp = next_dp

    # The answer is the minimum length value among all states.
    return min(dp.values())

# Example usage:
print(minConcatenatedLength(["aa", "ab", "bc"]))  # Expected output: 4
print(minConcatenatedLength(["ab", "b"]))           # Expected output: 2
print(minConcatenatedLength(["aaa", "c", "aba"]))     # Expected output: 6
← Back to All Questions