#3271

Medium

LeetCode Problem Workspace

Hash Divided String

Hash Divided String requires splitting a string into equal parts and combining character values modulo 26 to form a new string efficiently.

string simulation

Problem Statement

Given a string s of length n and an integer k, divide s into n/k equal substrings. Each substring should have exactly k characters. Then, compute a hash character for each substring by summing the positions of its letters in the alphabet, taking modulo 26, and converting back to a lowercase letter. Return the final string formed by concatenating all hash characters in order.

You must process the substrings sequentially from the beginning of s. Each letter 'a' to 'z' is mapped to values 0 to 25. After calculating the sum for each substring, take modulo 26 to stay within lowercase letters, then append the corresponding character to the result string. Ensure your solution handles strings where n is divisible by k and only contains lowercase English letters.

Examples

Example 1

Input: s = "abcd", k = 2

Output: "bf"

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"

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.

Solution Approach

Divide the string into substrings of length k

Iterate over the string in steps of k to extract each substring. This ensures every character is included and each substring is processed exactly once, following the string plus simulation pattern.

Compute hash for each substring

For each substring, convert each character to its position in the alphabet, sum these positions, take modulo 26, and convert back to a letter. This produces the correct hashed character for that substring.

Construct the result string

Append each hashed character to a result string in order. By processing substrings sequentially and building the result string step by step, the solution remains efficient and avoids common off-by-one errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is visited once during substring extraction and summing. Space complexity is O(n/k) for the resulting hashed string, plus temporary storage for substring sums.

What Interviewers Usually Probe

Check if you are correctly mapping characters to 0-25 values.
Confirm you handle strings of length divisible by k without skipping characters.
Ensure your modulo operation maps sums back to lowercase letters correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to take modulo 26 after summing character positions.
Incorrect substring slicing causing index errors or missing characters.
Mapping characters incorrectly, e.g., 'a' to 1 instead of 0.

Follow-up variants

Hash Divided String where k does not divide n, requiring handling remainder characters.
Use uppercase letters and adjust modulo mapping to 26 accordingly.
Instead of sum, use product of character positions modulo 26 for hashing.

FAQ

How do I map characters to numbers in Hash Divided String?

Map 'a' to 0, 'b' to 1, ..., 'z' to 25. Sum these for each substring and take modulo 26 to get the hashed character.

Can k be larger than the string length?

No, k must be less than or equal to the string length since each substring has exactly k characters.

What if the string length is not divisible by k?

This problem guarantees the string length is divisible by k, so no remainder handling is needed.

Is there a faster way than summing each substring manually?

Because each character must contribute to the sum, O(n) iteration is required; no asymptotically faster method exists.

Does GhostInterview provide hints for the string plus simulation pattern?

Yes, it guides through substring splitting, character position sums, and modulo mapping specifically for this hashing pattern.

terminal

Solution

Solution 1: Simulation

We can simulate the process according to the steps described in the problem.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        ans = []
        for i in range(0, len(s), k):
            t = 0
            for j in range(i, i + k):
                t += ord(s[j]) - ord("a")
            hashedChar = t % 26
            ans.append(chr(ord("a") + hashedChar))
        return "".join(ans)

Continue Practicing

#3248 snake in matrix #3324 find the sequence of strings appeared on the screen #3174 clear digits