Scale Engineer

Hash Divided String

Med
#2903Time: O(n). The outer loop runs `n/k` times. Inside, creating a substring of length `k` takes O(k) time, and iterating over it also takes O(k) time. Total time is `(n/k) * (O(k) + O(k)) = O(n)`.Space: O(k + n/k). `O(k)` space is required for the temporary `chunk` string in each iteration, and `O(n/k)` space is needed for the `StringBuilder` that stores the result.
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem description into code. It involves iterating through the string s in chunks of size k, creating a substring for each chunk, and then processing each substring to calculate the hash character. A StringBuilder is used to efficiently build the final result string.

Algorithm

  • Initialize an empty StringBuilder called result.
  • Loop from i = 0 to s.length() - 1 with a step of k.
  • Inside the loop, create a substring chunk from index i to i + k.
  • Initialize currentSum = 0.
  • Iterate through each character of the chunk.
  • For each character, add its hash value (char - 'a') to currentSum.
  • After iterating through the chunk, calculate hashedValue = currentSum % 26.
  • Convert hashedValue to its corresponding character and append it to result.
  • After the main loop, convert result to a string and return it.

Walkthrough

The algorithm proceeds by dividing the string into n/k segments. A loop iterates with a step of k, and in each step, s.substring(i, i + k) is called to extract the current chunk. While this is conceptually simple, creating a new substring object in each iteration introduces memory and performance overhead. For each extracted substring, we then iterate through its characters to compute the sum of their hash values (char - 'a'). The sum is taken modulo 26, converted back to a character, and appended to a StringBuilder. This avoids the high cost of repeated string concatenation in Java.

class Solution {    public String hashDividedString(String s, int k) {        StringBuilder result = new StringBuilder();        for (int i = 0; i < s.length(); i += k) {            String chunk = s.substring(i, i + k);            int currentSum = 0;            for (char c : chunk.toCharArray()) {                currentSum += c - 'a';            }            int hashedValue = currentSum % 26;            char hashedChar = (char) ('a' + hashedValue);            result.append(hashedChar);        }        return result.toString();    }}

Complexity

Time

O(n). The outer loop runs `n/k` times. Inside, creating a substring of length `k` takes O(k) time, and iterating over it also takes O(k) time. Total time is `(n/k) * (O(k) + O(k)) = O(n)`.

Space

O(k + n/k). `O(k)` space is required for the temporary `chunk` string in each iteration, and `O(n/k)` space is needed for the `StringBuilder` that stores the result.

Trade-offs

Pros

  • The code is very readable and closely follows the logic described in the problem statement.

Cons

  • Creates n/k new substring objects, which leads to unnecessary memory allocation and garbage collection overhead. This can be less performant than direct character access.

Solutions

class Solution {public  String stringHash(String s, int k) {    StringBuilder ans = new StringBuilder();    int n = s.length();    for (int i = 0; i < n; i += k) {      int t = 0;      for (int j = i; j < i + k; ++j) {        t += s.charAt(j) - 'a';      }      int hashedChar = t % 26;      ans.append((char)('a' + hashedChar));    }    return ans.toString();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem