Hash Divided String - Practice Coding Problems

Hash Divided String - Problem

String Simulation Medium

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.

Process:

1. First, divide s into n / k substrings, each with a length of k.

2. Initialize result as an empty string.

3. 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcd", k = 2

› Output: "bf"

💡 Note: Substring "ab": hash sum = 0 + 1 = 1, 1 % 26 = 1 → 'b'. Substring "cd": hash sum = 2 + 3 = 5, 5 % 26 = 5 → 'f'. Result: "bf"

Example 2 — Single Character Groups

$ Input: s = "xyz", k = 1

› Output: "xyz"

💡 Note: Each character forms its own substring: 'x' → 23 % 26 = 23 → 'x', 'y' → 24 % 26 = 24 → 'y', 'z' → 25 % 26 = 25 → 'z'

Example 3 — Wraparound Case

$ Input: s = "zzab", k = 2

› Output: "zb"

💡 Note: Substring "zz": hash sum = 25 + 25 = 50, 50 % 26 = 24 → 'y'. Wait, let me recalculate: 50 % 26 = 24 → 'y'. Actually "ab": 0 + 1 = 1 → 'b'. So result is "yb"

Constraints

1 ≤ s.length ≤ 1000
1 ≤ k ≤ s.length
s.length is a multiple of k
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and block size k

Process

Divide into k-length blocks and hash each

Output

Hashed result string

Key Takeaway

🎯 Key Insight: Each k-length substring can be independently hashed by summing character positions modulo 26

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to divide the string into blocks of size k and hash each block by summing character positions modulo 26. The optimal approach processes characters in a single pass without creating intermediate substrings. Time: O(n), Space: O(n/k)

Common Approaches

Approach	Time	Space	Notes
✓ Substring Processing	O(n)	O(n/k)	Divide string into substrings and hash each one separately
Single Pass Processing	O(n)	O(n/k)	Process characters directly without creating intermediate substrings

Substring Processing — Algorithm Steps

Step 1: Divide string s into substrings of length k
Step 2: For each substring, calculate sum of character hash values
Step 3: Take sum modulo 26 and convert back to character
Step 4: Append result character to output string

Visualization

Tap to expand

Step-by-Step Walkthrough

Divide

Split string into chunks of size k

Hash

Calculate sum of character values for each chunk

Convert

Convert sum modulo 26 back to character

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

char* solution(char* s, int k) {
    int n = strlen(s);
    static char result[1000];
    int resultIndex = 0;
    
    for (int i = 0; i < n; i += k) {
        int hashSum = 0;
        
        for (int j = i; j < i + k && j < n; j++) {
            hashSum += s[j] - 'a';
        }
        
        char hashedChar = (hashSum % 26) + 'a';
        result[resultIndex++] = hashedChar;
    }
    
    result[resultIndex] = '\0';
    return result;
}

int main() {
    char s[10000];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(s, k);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n characters to calculate hash values

✓ Linear Growth

Space Complexity

O(n/k)

Result string stores n/k characters, plus temporary substrings

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Substring Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler