Skip to main content
Talentd

Check Distances Between Same Letters - Solution & Explanation

EasyArrayHash TableString15 min read
Practice this problem

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 <= 52
  • s consists only of lowercase English letters.
  • Each letter appears in s exactly twice.
  • distance.length == 26
  • 0 <= 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.

Approach 1: Approach 1: Using Sorting

This approach involves sorting the input data to facilitate easier searching and manipulation. Once the data is sorted, various techniques can be applied to efficiently find the required solution. Sorting helps in reducing the average time complexity for performing operations such as searching or eliminating duplicate values.

This solution uses C's built-in qsort function to sort the array. This function takes a comparator function that defines the sorting order. Sorting is followed by operations that can leverage the sorted nature of the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in-place.

Try this approach in the editor →

Approach 2: Approach 2: Using Hash Map

This approach employs a hash map (or dictionary) to track occurrences of elements efficiently. Hash maps offer average time complexity for insertion and lookup operations that is linear with low constants, making them advantageous for frequency counting and eliminating duplicate elements.

This C program creates a simple hash table to count occurrences of elements. Given constraints are necessary for defining the hash table size.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for processing elements.
Space Complexity: O(k) where k is the range of input values.

Try this approach in the editor →

Approach 3: Array or Hash Table

We can use a hash table d to record the indices of each letter's occurrences. Then, traverse the hash table and check if the difference between the indices of each letter equals the corresponding value in the distance array. If any discrepancy is found, return false. If the traversal completes without discrepancies, return true.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, which in this case is the set of lowercase letters.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in-place.

Approach 2: Using Hash Map

Time Complexity: O(n) for processing elements.
Space Complexity: O(k) where k is the range of input values.

Array or Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting Character IndicesO(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 TrackingO(n)O(1)General case and interview settings where linear scan with constant memory is preferred

Video Solution

2399. Check Distances Between Same Letters | Leetcode Weekly Contest 309 | LeetCode 2399 • Bro Coders • 1,788 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check Distances Between Same Letters easy or hard?
Check Distances Between Same Letters is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge focuses on correct index tracking and understanding how to compute character distance within a string.
Check Distances Between Same Letters Python/Java solution
In Python or Java, store the first index of each character in a dictionary or integer array. When the character appears again, compute the gap between indices and compare it with distance[char - 'a']. The implementation typically takes fewer than 15 lines and runs in O(n) time.
How to solve Check Distances Between Same Letters in O(n)?
Scan the string once while storing the first occurrence of each character in a hash map or array of size 26. When the same character appears again, compute the distance using index difference minus one and compare it with the expected value in the distance array. If any mismatch occurs, return false immediately.
What is the best approach for Check Distances Between Same Letters?
The hash map approach is the most efficient. Store the first index of each character while scanning the string, then compute the distance when the character appears again. This method runs in O(n) time with O(1) extra space because the alphabet size is fixed at 26.
Is Check Distances Between Same Letters asked at Google/Amazon/Meta?
This problem is categorized as an easy string and hash table question and appears in coding practice sets commonly used for interview preparation. Variations of string distance validation and character index tracking frequently appear in interviews at large tech companies.
What data structure is used in Check Distances Between Same Letters?
The main data structure is a hash map or a fixed-size array used to store the first occurrence index of each character. The distance array is also accessed directly to validate the required spacing between duplicate characters.
What is the time complexity of Check Distances Between Same Letters?
The optimal solution runs in O(n) time, where n is the length of the string. Each character is processed once, and hash lookups or array accesses take constant time. Space complexity is O(1) because only 26 character positions are stored.

Ready to solve this problem?

Practice Check Distances Between Same Letters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shortest Distance to a Character

Next

Two Sum