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.
We will divide the string s into multiple substrings each of length k. For each substring, we calculate the sum of hash values of its characters and use the modulus operator to find the appropriate character in the alphabet to append to the result string.
The solution works by dividing s into equal parts of k and calculating the sum of alphabetical indices of each substring, then taking the modulus by 26 to find the corresponding character to add to the result string.
Time Complexity: O(n), with n being the length of s. Space Complexity: O(n/k).
We can simulate the process according to the steps described in the problem.
Traverse the string s, and each time take k characters, calculate the sum of their hash values, denoted as t. Then, take t modulo 26 to find the corresponding character and add it to the end of the result string.
Finally, return the result string.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer string, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Hashing Using Substring Sums | Time Complexity: O(n), with |
| Simulation | — |
| 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. |
Hash Divided String || LeetCode Biweekly Contest 138 || Leetcode Solution • codi • 203 views views
Watch 6 more video solutions →Practice Hash Divided String with our built-in code editor and test cases.
Practice on FleetCode