Hash Divided String
MedPrompt
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 <= 100k <= s.length <= 1000s.lengthis divisible byk.sconsists 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
StringBuildercalledresult. - Loop from
i = 0tos.length() - 1with a step ofk. - Inside the loop, create a substring
chunkfrom indexitoi + k. - Initialize
currentSum = 0. - Iterate through each character of the
chunk. - For each character, add its hash value (
char - 'a') tocurrentSum. - After iterating through the chunk, calculate
hashedValue = currentSum % 26. - Convert
hashedValueto its corresponding character and append it toresult. - After the main loop, convert
resultto 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/knew substring objects, which leads to unnecessary memory allocation and garbage collection overhead. This can be less performant than direct character access.
This is a more efficient approach that avoids creating intermediate substring objects. It processes the input string s in a single pass using a nested loop structure. The outer loop marks the beginning of each k-length chunk, and the inner loop iterates through the characters of that chunk using charAt() to calculate the sum, thus minimizing memory overhead.
Algorithm
- Initialize an empty
StringBuildercalledresult. - Loop with an outer index
ifrom0tos.length() - 1with a step ofk. - Inside the outer loop, initialize
currentSum = 0. - Start an inner loop with index
jfromitoi + k - 1. - In the inner loop, get the character
s.charAt(j)and add its hash value (s.charAt(j) - 'a') tocurrentSum. - After the inner loop completes, calculate
hashedValue = currentSum % 26. - Convert
hashedValueto its corresponding character and append it toresult. - After the outer loop, convert
resultto a string and return it.
Walkthrough
This method optimizes the process by directly accessing characters from the input string s instead of creating substrings. We use a StringBuilder for efficient result construction. The algorithm employs a nested loop. The outer loop iterates through the string with a step of k, defining the start of each chunk. The inner loop then iterates k times to cover all characters in the current chunk. Inside the inner loop, s.charAt(j) retrieves each character, its hash value is computed and added to a running sum for the chunk. Once the inner loop finishes, the sum is processed (modulo 26) and the resulting character is appended to the StringBuilder. This eliminates the overhead of temporary object creation from the substring-based approach.
class Solution { public String hashDividedString(String s, int k) { StringBuilder result = new StringBuilder(); int n = s.length(); for (int i = 0; i < n; i += k) { int currentSum = 0; for (int j = i; j < i + k; j++) { currentSum += s.charAt(j) - 'a'; } char hashedChar = (char) ('a' + (currentSum % 26)); result.append(hashedChar); } return result.toString(); }}Complexity
Time
O(n). The nested loops effectively iterate over each character of the string `s` exactly once. The outer loop runs `n/k` times and the inner loop runs `k` times, for a total of `(n/k) * k = n` constant-time operations.
Space
O(n/k). The space required is primarily for the `StringBuilder` to store the output string, which has a length of `n/k`. This is the minimum possible space complexity as it's required for the output itself.
Trade-offs
Pros
Highly efficient as it avoids creating intermediate string objects, reducing memory usage and garbage collection pressure.
Processes the string in a single pass with direct character access, which is generally faster.
Cons
The nested loop indexing (
jfromitoi+k) might be considered slightly less intuitive than iterating over a pre-made substring, but it's a standard and efficient pattern.
Solutions
Solution
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(); }}class Solution {public: string stringHash(string s, int k) { string ans; 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[j] - 'a'; } int hashedChar = t % 26; ans += ('a' + hashedChar); } return ans; }};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)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.