Watch 7 video solutions for Hash Divided String, a medium level problem involving String, Simulation. This walkthrough by codi has 203 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s of length n and an integer k, where n is a multiple of k. Your task is to hash the string s into a new string called result, which has a length of n / k.
First, divide s into n / k substrings, each with a length of k. Then, initialize result as an empty string.
For each substring in order from the beginning:
'a' → 0, 'b' → 1, ..., 'z' → 25).hashedChar.hashedChar.result.Return result.
Example 1:
Input: s = "abcd", k = 2
Output: "bf"
Explanation:
First substring: "ab", 0 + 1 = 1, 1 % 26 = 1, result[0] = 'b'.
Second substring: "cd", 2 + 3 = 5, 5 % 26 = 5, result[1] = 'f'.
Example 2:
Input: s = "mxz", k = 3
Output: "i"
Explanation:
The only substring: "mxz", 12 + 23 + 25 = 60, 60 % 26 = 8, result[0] = 'i'.
Constraints:
1 <= k <= 100k <= s.length <= 1000s.length is divisible by k.s consists only of lowercase English letters.Problem Overview: You are given a lowercase string s and an integer k. Split the string into consecutive substrings of length k. For each substring, compute the sum of the alphabetical indices of its characters (a = 0, b = 1, ..., z = 25), take the result modulo 26, and convert it back into a character. Concatenate these characters to form the final hashed string.
Approach 1: Direct Simulation (O(n) time, O(n/k) space)
The most straightforward solution is to simulate exactly what the problem describes. Iterate through the string in steps of k, extract each substring, and compute the sum of character values. Each character contributes ord(c) - ord('a'). After summing the values for the k characters, compute sum % 26 and convert the result back into a character using 'a' + value. Append that character to the result string. Every character in s is processed exactly once, so the total time complexity is O(n), with O(n/k) space for the output. This approach is clean, readable, and aligns directly with the problem statement.
This method is essentially a simulation problem built on simple string traversal. Since the substring size is fixed, the logic stays predictable and easy to reason about.
Approach 2: Prefix Sum Hashing (O(n) time, O(n) space)
If you want to avoid recomputing character sums for each substring independently, you can precompute a prefix sum array of character values. Create an array where prefix[i] stores the total value of characters from index 0 to i-1. The sum for any substring s[i ... i+k-1] can then be calculated in constant time using prefix[i+k] - prefix[i]. After retrieving the substring sum, apply modulo 26 and convert it to a character.
This technique uses a classic hashing-style idea where substring values are derived from cumulative sums. It still runs in O(n) time but uses O(n) extra space for the prefix array. In practice, the direct simulation approach is usually simpler and just as efficient for this problem.
Recommended for interviews: Interviewers typically expect the direct simulation solution. It processes each character once and maps directly to the problem definition, giving O(n) time and minimal extra memory. Mentioning prefix sums shows deeper understanding of substring sum optimization, but the simple simulation is already optimal and easier to implement correctly under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n) | O(n/k) | Best general solution. Simple implementation that directly follows the problem statement. |
| Prefix Sum Hashing | O(n) | O(n) | Useful when many substring sum queries are needed or when demonstrating prefix sum optimization. |