Hash Divided String — Solution in Python, Java & C++
Hash Divided String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Hash Divided String is a medium coding problem on strings and simulation, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Simulation
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of length n and an integer k, where n is a multiple of k.
Cut s into n / k consecutive pieces of length k. For each piece, in order:
- give every letter its hash value — its index in the alphabet (
'a'is 0,'b'is 1, …,'z'is 25); - add the hash values of the piece and take the sum modulo 26;
- append the letter with that index to the result.
Return the resulting string of length n / k.
Example 1
Input: s = "abcd", k = 2
Output: bf
Explanation: "ab" sums to 0 + 1 = 1 → 'b'; "cd" sums to 2 + 3 = 5 → 'f'.
Example 2
Input: s = "mxz", k = 3
Output: i
Explanation: 12 + 23 + 25 = 60, and 60 mod 26 = 8 → 'i'.
Example 3
Input: s = "zzab", k = 1
Output: zzab
Explanation: With pieces of one letter each, every letter maps to itself.
Constraints
1 <= k <= 100k <= s.length <= 1000s.length % k == 0s consists only of lowercase English letters
Hints for Hash Divided String
Hint 1
The pieces are independent: process
sin steps ofk.Hint 2
Sum
s[j] - 'a'over the piece; the largest possible sum is100 * 25, far from overflowing.Hint 3
Reduce the sum modulo 26 and turn it back into a letter with
'a' + value.
How to solve Hash Divided String
A direct simulation: each output letter depends only on its own block of k input letters.
Approach
- For
i = 0, k, 2k, …: sums[j] - 'a'forjin[i, i + k). - Append the letter
'a' + (sum mod 26). - Return the built string.
Why it works
The statement defines each output character from one block, and the loop visits the blocks in order exactly once.
Complexity
- Time —
O(n) - Space —
O(n / k) for the output
Pitfalls
- Use the letter's index (
'a'= 0), not its character code, before taking the modulus.
Reference solution
Python
def stringHash(s: str, k: int) -> str:
out = []
for i in range(0, len(s), k):
total = sum(ord(c) - 97 for c in s[i:i + k])
out.append(chr(97 + total % 26))
return "".join(out)Java
public static String stringHash(String s, int k) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i += k) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += s.charAt(j) - 'a';
sb.append((char) ('a' + sum % 26));
}
return sb.toString();
}C++
string stringHash(string s, int k) {
string out;
for (int i = 0; i < (int) s.size(); i += k) {
int sum = 0;
for (int j = i; j < i + k; j++) sum += s[j] - 'a';
out += (char) ('a' + sum % 26);
}
return out;
}JavaScript
var stringHash = function(s, k) {
var out = [];
for (var i = 0; i < s.length; i += k) {
var sum = 0;
for (var j = i; j < i + k; j++) sum += s.charCodeAt(j) - 97;
out.push(String.fromCharCode(97 + sum % 26));
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings