Skip to main content
Talentd

Hash Divided String - Solution & Explanation

MediumStringSimulation12 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • The hash value of a character is the index of that character in the English alphabet (e.g., 'a' → 0, 'b' → 1, ..., 'z' → 25).
  • Calculate the sum of all the hash values of the characters in the substring.
  • Find the remainder of this sum when divided by 26, which is called hashedChar.
  • Identify the character in the English lowercase alphabet that corresponds to hashedChar.
  • Append that character to the end of 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 <= 100
  • k <= s.length <= 1000
  • s.length is divisible by k.
  • s consists only of lowercase English letters.

Approach Overview

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 1: Hashing Using Substring Sums

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), with n being the length of s. Space Complexity: O(n/k).

Try this approach in the editor →

Approach 2: Simulation

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hashing Using Substring Sums

Time Complexity: O(n), with n being the length of s. Space Complexity: O(n/k).

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n)O(n/k)Best general solution. Simple implementation that directly follows the problem statement.
Prefix Sum HashingO(n)O(n)Useful when many substring sum queries are needed or when demonstrating prefix sum optimization.

Video Solution

Hash Divided String || LeetCode Biweekly Contest 138 || Leetcode Solution • codi • 203 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Hash Divided String easy or hard?
Hash Divided String is classified as a Medium problem but conceptually straightforward. The main challenge is translating the hashing rule correctly and iterating through fixed-size substrings without off-by-one errors.
Hash Divided String Python/Java solution
In Python or Java, iterate over the string with a step size of k, compute the sum of character values for each block, apply modulo 26, and append the resulting character. The logic is identical across languages and runs in O(n) time.
How to solve Hash Divided String in O(n)?
Traverse the string in steps of k. For each substring, sum the character indices using (c - 'a'), compute sum % 26, and append the corresponding character ('a' + value) to the result. Since every character contributes to exactly one group, the algorithm runs in linear time.
What is the best approach for Hash Divided String?
The optimal approach is direct simulation. Iterate through the string in chunks of size k, compute the sum of character values (a=0 to z=25), take the sum modulo 26, and convert it back to a character. This processes each character once, giving O(n) time complexity and minimal additional memory.
Is Hash Divided String asked at Google/Amazon/Meta?
Problems like Hash Divided String appear in coding interviews at large tech companies because they test string manipulation, modular arithmetic, and careful implementation. While the exact problem may vary, similar string hashing and simulation tasks are common in Amazon, Google, and Meta interview prep sets.
What data structure is used in Hash Divided String?
The solution mainly uses basic string traversal and arithmetic operations. Some implementations optionally use prefix sum arrays to compute substring sums quickly, which is a common technique in hashing and range-query problems.
What is the time complexity of Hash Divided String?
The time complexity is O(n), where n is the length of the string. Each character is visited exactly once while computing substring sums. Space complexity is O(n/k) for the resulting hashed string.

Ready to solve this problem?

Practice Hash Divided String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring