Hash Divided String

MEDIUM

Description

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

Checkout 2 different approaches to solve Hash Divided String. Click on different approaches to view the approach and algorithm in detail.

Iterating Through Substrings

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Hash Divided String. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Hash Divided String

Data Structures:

String