Check Distances Between Same Letters - Video Solutions
2399. Check Distances Between Same Letters | Leetcode Weekly Contest 309 | LeetCode 2399
Check Distances Between Same Letters - Video Solution
Watch 10 video solutions for Check Distances Between Same Letters, a easy level problem involving Array, Hash Table, String. This walkthrough by Bro Coders has 1,788 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 ith letter is distance[i]. If the ith letter does not appear in s, then distance[i] can be ignored.
Return true if s is a well-spaced string, otherwise return false.
Example 1:
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 Explanation: - 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1. - 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3. - 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0. Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored. Return true because s is a well-spaced string.
Example 2:
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 Explanation: - 'a' appears at indices 0 and 1 so there are zero letters between them. Because distance[0] = 1, s is not a well-spaced string.
Constraints:
2 <= s.length <= 52sconsists only of lowercase English letters.- Each letter appears in
sexactly twice. distance.length == 260 <= distance[i] <= 50
Approach Overview
Problem Overview: You are given a string s and an integer array distance of size 26. Each character in s appears exactly twice. The number of characters between the two occurrences of a letter must match the value stored at its index in distance. The task is to verify whether the string satisfies this rule for every character.
Approach 1: Using Sorting (O(n log n) time, O(n) space)
This method records the indices where each character appears, then sorts the recorded pairs of indices to compute distances. You first iterate through the string and push (character, index) pairs into a list. After sorting by character, identical letters become adjacent, making it easy to calculate the gap between their indices. For each pair, compute index2 - index1 - 1 and compare it with distance[char - 'a']. Sorting introduces O(n log n) time complexity, while storing indices requires O(n) extra space. This approach is straightforward and works well when you're already manipulating ordered character-index pairs.
Approach 2: Using Hash Map (O(n) time, O(1) space)
A more efficient solution stores the first occurrence of each character using a hash map (or fixed array of size 26). Iterate through the string once. When you encounter a character for the first time, record its index. When you see it again, compute the distance between the two positions using currentIndex - firstIndex - 1 and compare it with the expected value in the distance array. Because each lookup in the hash map is O(1), the full scan runs in linear time. The extra memory stays constant since only 26 lowercase letters are possible.
This approach relies on fast lookups and a single pass over the string, which is why it is commonly categorized under hash table and string problems. The input array is also accessed directly as an array, keeping operations simple and cache-friendly.
Recommended for interviews: The hash map approach. Interviewers expect candidates to recognize that only the first index of each character matters. Recording it and validating the distance during the second occurrence produces an O(n) solution with constant space. Discussing the sorting approach first can demonstrate baseline reasoning, but implementing the hash map version shows stronger algorithmic thinking and familiarity with common string-processing patterns.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Character Indices | O(n log n) | O(n) | When storing and processing ordered character-index pairs or when sorting is already part of the pipeline |
| Hash Map / First Occurrence Tracking | O(n) | O(1) | General case and interview settings where linear scan with constant memory is preferred |