Check Distances Between Same Letters - Practice Coding Problems

Check Distances Between Same Letters - Problem

You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactly twice. You are also given a 0-indexed integer array distance of length 26.

Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' → 0, 'b' → 1, 'c' → 2, ..., 'z' → 25).

In a well-spaced string, the number of letters between the two occurrences of the i^th letter is distance[i]. If the i^th letter does not appear in s, then distance[i] can be ignored.

Return true if s is a well-spaced string, otherwise return false.

Input & Output

Example 1 — Basic Valid Case

$ Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

› Output: true

💡 Note: Character 'a' appears at positions 0,2 with 1 character between (distance[0]=1 ✓). Character 'b' appears at positions 1,5 with 3 characters between (distance[1]=3 ✓). Character 'c' appears at positions 3,4 with 0 characters between (distance[2]=0 ✓).

Example 2 — Invalid Distance

$ Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

› Output: false

💡 Note: Character 'a' appears at positions 0,1 with 0 characters between, but distance[0]=1 requires 1 character between them.

Example 3 — Perfect Adjacent Match

$ Input: s = "aa", distance = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

› Output: true

💡 Note: Character 'a' appears at positions 0,1 with 0 characters between, matching distance[0]=0 exactly.

Constraints

2 ≤ s.length ≤ 52
s consists only of lowercase English letters
Each letter appears in s exactly twice
distance.length == 26
0 ≤ distance[i] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

String with duplicate characters and distance requirements

Process

Calculate actual distances between character pairs

Output

Return true if all distances match requirements

Key Takeaway

🎯 Key Insight: Use hash map to track first occurrences and validate distances immediately on second occurrence

Asked in

G Google 12 f Meta 8 M Microsoft 6

The optimal approach uses a hash map to track first occurrences and validate distances on second occurrences in a single pass. Key insight: Instead of finding all pairs first, validate immediately when encountering the second occurrence of each character. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Find All Pairs	O(n²)	O(1)	For each character, find both positions and check the distance
Hash Map - Single Pass	O(n)	O(1)	Track first occurrence positions and validate on second occurrence

Brute Force - Find All Pairs — Algorithm Steps

Step 1: For each character, scan string to find both positions
Step 2: Calculate distance between positions
Step 3: Compare with required distance from array

Visualization

Tap to expand

Step-by-Step Walkthrough

Find First 'a'

Scan from position to find matching character

Calculate Distance

Count characters between the two positions

Validate

Check if distance matches requirement

Code -

solution.c — C

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

bool solution(char* s, int* distance) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        char ch = s[i];
        int charIdx = ch - 'a';
        
        // Find the other occurrence of this character
        for (int j = i + 1; j < n; j++) {
            if (s[j] == ch) {
                // Check if distance matches
                int actualDistance = j - i - 1;
                if (actualDistance != distance[charIdx]) {
                    return false;
                }
                break;
            }
        }
    }
    return true;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char distanceStr[10000];
    fgets(distanceStr, sizeof(distanceStr), stdin);
    
    // Parse array manually
    int distance[26];
    char* token = strtok(distanceStr + 1, ",");
    int idx = 0;
    while (token != NULL && idx < 26) {
        distance[idx++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    bool result = solution(s, distance);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each character position, we scan the entire string to find its pair

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for tracking positions

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

445 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

Brute Force - Find All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler