Hash Divided String

Medium
1771.

Hash Divided String

Hash Divided String is a medium coding problem on strings and simulation, asked in Google interviews.

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 <= 100
  • k <= s.length <= 1000
  • s.length % k == 0
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var stringHash = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • k <= s.length <= 1000
  • s.length % k == 0
  • s consists only of lowercase English letters

Hints for Hash Divided String

  1. Hint 1

    The pieces are independent: process s in steps of k.

  2. Hint 2

    Sum s[j] - 'a' over the piece; the largest possible sum is 100 * 25, far from overflowing.

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

  1. For i = 0, k, 2k, …: sum s[j] - 'a' for j in [i, i + k).
  2. Append the letter 'a' + (sum mod 26).
  3. 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