Uber
Online AssessmentNew Network Protocol
A string must be transferred using a custom network protocol. The protocol processes the string as follows:
- Each pair of characters in the string is processed together.
- If any pair contains matching characters (e.g., 'aa', 'bb'), it requires an additional sameTime seconds.
- The string can be split into substrings before transmission, with each partition cut adding partitionTime seconds.
Calculate the minimum possible total extra time required, which is the sum of:
- Time for processing pairs with matching characters.
- Time for creating partitions.
- ▸Line 1: Integer partitionTime (or sameTime).
- ▸Line 2: Integer sameTime (or partitionTime).
- ▸Line 3: String s to transfer.
- ▸Print an integer representing the minimum possible total extra time.
- 1 <= |s| <= 2000
- 1 <= sameTime, partitionTime <= 10^5
- String s consists of lowercase English letters.
4 1 abcabcc
5
Two optimal approaches exist:
1. Split into ["abc", "abcc"]: partitionTime = 4, matching pairs in "abcc" = 1 ('cc') * 1 = 1. Total = 4 + 1 = 5.
2. Keep as single string ["abcabcc"]: 0 partition cuts, 5 matching pairs ('aa', 'bb', 'cc', 'cc', 'cc') * 1 = 5. Total = 5.
1. For any substring s[j..i-1], if character c appears count[c] times, the number of matching pairs is sum_c count[c] * (count[c] - 1) / 2. 2. Dynamic Programming: - Let `dp[i]` be the minimum extra time to transmit prefix s[0..i-1]. - Base case: `dp[0] = 0`. - Transitions: For each ending position i from 1 to n: - Iterate starting position j from i - 1 down to 0 while maintaining matching pairs incrementally in O(1). - Partition cost is 0 if j == 0 (no cut needed), or partitionTime if j > 0. - `dp[i] = min(dp[i], dp[j] + pairs * sameTime + (j > 0 ? partitionTime : 0))`. 3. Time Complexity: O(N^2), Space Complexity: O(N).