LeetCode 3271 - Hash Divided String

Difficulty: 🟡 Medium
Topics: String, Simulation

Solution

Problem Understanding

The problem asks us to compute a hashed string from an input string s by dividing it into equal-length substrings and then mapping each substring to a single character using a simple hashing function. Specifically, for each substring of length k, we compute the sum of the positions of its characters in the English alphabet (where 'a' maps to 0, 'b' to 1, ..., 'z' to 25), then take the sum modulo 26 to find the resulting character. This process continues sequentially for all substrings, building the result string one character at a time.

The input consists of a string s of lowercase letters and an integer k such that the length of s is divisible by k. This guarantees that the string can be split into equal-length substrings without leftover characters. The constraints indicate that the input string can be at most 1000 characters long, and k can be at most 100. This makes it feasible to compute the sum of character values for each substring directly without sophisticated optimizations.

Important edge cases include the minimum and maximum values of k, strings consisting of repeated characters, and cases where the resulting hash wraps around modulo 26.

Approaches

The brute-force approach is straightforward. First, split the string into n/k substrings. For each substring, calculate the sum of character indices manually and then compute the modulo 26 to map it to a letter. Append each resulting character to the result. This approach is correct because it directly implements the problem statement. However, it requires iterating through all characters of s for each substring, which can be slightly inefficient if k is large, though still manageable within the given constraints.

A more optimal approach observes that the brute-force approach is already efficient for the problem size. The main improvement is in code clarity and avoiding unnecessary conversions. By computing the hash using character arithmetic (ord(char) - ord('a')) in a single loop, we reduce intermediate steps and maintain an O(n) runtime.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n/k)	Split string, sum character indices per substring, append hash
Optimal	O(n)	O(n/k)	Single-pass calculation using arithmetic directly, no extra arrays

Algorithm Walkthrough

Compute the number of substrings as num_substrings = n / k. This tells us how many characters the result string will have.
Initialize an empty string result to build the hashed output.
Iterate over each substring. The start of a substring is i*k and the end is (i+1)*k.
For each substring, initialize a variable substring_sum to 0.
Iterate over each character in the substring, compute its alphabetical index using ord(char) - ord('a'), and add it to substring_sum.
After processing the substring, compute hashed_char_index = substring_sum % 26 to get the final character index modulo 26.
Convert hashed_char_index back to a character using chr(hashed_char_index + ord('a')) and append it to result.
After all substrings are processed, return result.

Why it works: This algorithm preserves the problem invariant that each substring contributes exactly one character to the result. Using the modulo 26 operation ensures that the hashed character is always a valid lowercase English letter. Summing character indices directly maintains correctness as defined by the problem statement.

Python Solution

class Solution:
    def stringHash(self, s: str, k: int) -> str:
        n = len(s)
        result = ""
        for i in range(0, n, k):
            substring_sum = 0
            for char in s[i:i+k]:
                substring_sum += ord(char) - ord('a')
            hashed_char_index = substring_sum % 26
            result += chr(hashed_char_index + ord('a'))
        return result

This Python implementation follows the algorithm exactly. We iterate through s in steps of k to get each substring. For each substring, the sum of character indices is computed using ord(char) - ord('a'). The modulo 26 result is then converted back into a character and appended to the result string. This ensures that every substring contributes exactly one hashed character to the output.

Go Solution

func stringHash(s string, k int) string {
    n := len(s)
    result := make([]byte, 0, n/k)
    
    for i := 0; i < n; i += k {
        substringSum := 0
        for j := i; j < i+k; j++ {
            substringSum += int(s[j] - 'a')
        }
        hashedChar := byte(substringSum%26) + 'a'
        result = append(result, hashedChar)
    }
    
    return string(result)
}

In Go, we use a byte slice result with preallocated capacity to efficiently build the string. The character arithmetic is the same as in Python. Converting from a byte slice to a string at the end produces the final hashed string. Using a slice avoids repeated string concatenation overhead in Go.

Worked Examples

Example 1: s = "abcd", k = 2

Substring	Character indices	Sum	Sum % 26	Result char	Result so far
"ab"	0, 1	1	1	'b'	"b"
"cd"	2, 3	5	5	'f'	"bf"

Example 2: s = "mxz", k = 3

Substring	Character indices	Sum	Sum % 26	Result char	Result so far
"mxz"	12, 23, 25	60	8	'i'	"i"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character of `s` is processed exactly once to compute its hash.
Space	O(n/k)	We store one character per substring in the result string.

The time complexity is linear because we iterate over all n characters once. Space complexity depends on the number of substrings, which is n/k, because each substring produces a single character in the result.

Test Cases

# Provided examples
assert Solution().stringHash("abcd", 2) == "bf"  # 2 substrings, each hashed correctly
assert Solution().stringHash("mxz", 3) == "i"   # single substring

# Minimum length
assert Solution().stringHash("a", 1) == "a"  # single character

# All same characters
assert Solution().stringHash("zzz", 1) == "zzz"  # each 'z' hashes to 'z'

# k equals length of string
assert Solution().stringHash("abcde", 5) == "k"  # sum 0+1+2+3+4=10, 10%26='k'

# Larger string
assert Solution().stringHash("abcdefghijklmnopqrstuvwxyz", 13) == "mp"  # two substrings

Test	Why
"abcd", 2	Validates basic example from problem
"mxz", 3	Single substring with modulo wrapping
"a", 1	Minimum input length
"zzz", 1	Repeated character handling
"abcde", 5	Entire string as single substring
"abcdefghijklmnopqrstuvwxyz", 13	Multiple substrings covering full alphabet

Edge Cases

One important edge case is when k equals 1. Each character of s becomes its own substring. The algorithm handles this correctly because the loop iterates with step size 1 and hashes each character individually. Another edge case occurs when k equals the length of s, meaning there is only a single substring. The modulo operation ensures the resulting character is within 'a' to 'z' even if the sum exceeds 26. A third edge case is when the string consists of repeated characters such as all 'z'. Summing these high values could exceed 26, but taking modulo 26 ensures proper wrapping to produce valid characters. Each of these cases is handled naturally by the character arithmetic and modulo operation.