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

Maximum Deletions on a String

Number: 2510

Difficulty: Hard

Paid? No

Companies: DE Shaw

Problem Description

Given a string s consisting only of lowercase English letters, you are allowed in one operation to either remove the entire string s or remove the first i letters of s if those i letters are exactly equal to the following i letters. The goal is to determine the maximum number of operations needed to eventually delete the whole string.

Key Insights

  • Use dynamic programming where dp[i] represents the maximum operations possible for the substring s[i:].
  • To decide if a deletion is allowed at index i, you need to quickly check whether s[i:i+x] equals s[i+x:i+2*x] for valid lengths x.
  • A rolling hash (or precomputed hash arrays) can speed up substring comparisons to achieve an efficient solution.
  • The recurrence will check every valid prefix deletion and update dp[i] accordingly; if no valid deletion exists, the whole substring is removed in one operation.

Space and Time Complexity

Time Complexity: O(n^2) in worst-case (optimized substring comparisons using rolling hash can make these checks faster) Space Complexity: O(n), for the dp array and the rolling hash arrays

Solution

We solve this problem using dynamic programming. Define dp[i] as the maximum number of operations needed to delete the substring s[i:].

For each index i from the end of the string to the beginning:

  • Initially, set dp[i] = 1 because you can always delete the entire substring s[i:] in one operation.
  • For every possible prefix length x (from 1 to half of the remaining length), check if the prefix s[i:i+x] is equal to the next x characters, s[i+x:i+2*x]. This check is efficiently done via a rolling hash.
  • If they are equal, update dp[i] = max(dp[i], 1 + dp[i+x]).
  • Return dp[0] as the answer.

The trick is to precompute the rolling hash for constant-time substring comparisons, which handles the frequent equality checks in the inner loop.

Code Solutions

# Python solution using Dynamic Programming with Rolling Hash

def max_deletions(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    # Base case: an empty string requires 0 operations.
    dp[n] = 0

    # Rolling hash parameters
    mod = 10**9 + 7
    base = 26

    # Precompute prefix hashes and powers of base
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + (ord(s[i]) - ord('a'))) % mod
        power[i+1] = (power[i] * base) % mod

    # Helper to get hash of substring s[l:r]
    def get_hash(l, r):
        return (prefix_hash[r] - prefix_hash[l] * power[r - l]) % mod

    # Iterate backwards to fill dp
    for i in range(n - 1, -1, -1):
        # Option to delete the whole substring at once
        dp[i] = 1
        # Check all valid prefix lengths x
        for x in range(1, (n - i) // 2 + 1):
            if get_hash(i, i + x) == get_hash(i + x, i + 2 * x):
                dp[i] = max(dp[i], 1 + dp[i + x])
    return dp[0]

# Example usage:
s = "aaabaab"
print(max_deletions(s))  # Expected output: 4
← Back to All Questions