Check Distances Between Same Letters solution and explanation
9 more videos on this problem
2399. Check Distances Between Same Letters | Leetcode Weekly Contest 309 | LeetCode 2399Bro Coders · 7:41 · 1K views
Leetcode 2399 Check Distances Between Same Letters | Maps | Coding Decoded SDE SheetCoding Decoded · 7:45 · 991 views
2399 Check Distances Between Same Letters | Zero to FAANG Kunal | Assignment Solution | LeetcodeProgrammers Zone · 12:23 · 707 views
Leetcode 2399 Check Distances Between Same LettersAlgorithmicIQ · 15:37 · 478 views
2399. Check Distances Between Same Letters (Leetcode Easy)Programming Live with Larry · 5:16 · 364 views
Leetcode 2399: Check Distances Between Same LettersAlgorithms Casts · 7:16 · 345 views
6167. Check Distances Between Same Letters || Leetcode Contest Easy|| CPP || Most Intuitive Sol 🤩🤩Coding Techniques with Komal | Newton School · 7:28 · 183 views
LeetCode 2399 | Check Distances Between Same Letters | Character Check | HashMap | JavaSleepy Cracker · 7:13 · 175 views
2399. Check Distances Between Same Letters || leetcode weekly contest || C++ || Hindi explanationCS warriors · 9:06 · 146 views
L467, №2399. Check Distances Between Same Letters / LeetcodeYersham · 11:01 · 115 views
The 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 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.
Approach 1: Approach 1: Using Sorting
def solve(arr):
arr.sort()
# Further operations for the solution after sorting
arr = [4, 2, 5, 1, 3]
solve(arr)import java.util.Arrays;
public class Solution {
public static void solve(int[] arr) {
Arrays.sort(arr);
// Further operations for the solution after sorting
}
public static void main(String[] args) {
int[] arr = {4, 2, 5, 1, 3};
solve(arr);
}
}#include <iostream>
#include <vector>
#include <algorithm>
void solve(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end());
// Further operations for the solution after sorting
}
int main() {
std::vector<int> arr = {4, 2, 5, 1, 3};
solve(arr);
return 0;
}function solve(arr) {
arr.sort((a, b) => a - b);
// Further operations for the solution after sorting
}
let arr = [4, 2, 5, 1, 3];
solve(arr);#include <stdio.h>
#include <stdlib.h>
int comparator(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
void solve(int arr[], int n) {
qsort(arr, n, sizeof(int), comparator);
// Further operations for the solution after sorting
}
int main() {
int arr[] = {4, 2, 5, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
solve(arr, n);
return 0;
}using System;
class Solution {
static void Solve(int[] arr) {
Array.Sort(arr);
// Further operations for the solution after sorting
}
static void Main() {
int[] arr = {4, 2, 5, 1, 3};
Solve(arr);
}
}This Python solution makes use of the in-built list sort function for efficient sorting, enabling easy handling of subsequent logic.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) because sorting is in-place.
Approach 2: Approach 2: Using Hash Map
def solve(arr):
frequency = {}
for num in arr:
frequency[num] = frequency.get(num, 0) + 1
# Further operations using the frequency dictionary
arr = [4, 2, 5, 1, 3, 2]
solve(arr)import java.util.HashMap;
public class Solution {
public static void solve(int[] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// Further operations using the map
}
public static void main(String[] args) {
int[] arr = {4, 2, 5, 1, 3, 2};
solve(arr);
}
}#include <iostream>
#include <unordered_map>
#include <vector>
void solve(const std::vector<int>& arr) {
std::unordered_map<int, int> map;
for (int num : arr) {
map[num]++;
}
// Further operations using the map
}
int main() {
std::vector<int> arr = {4, 2, 5, 1, 3, 2};
solve(arr);
return 0;
}function solve(arr) {
const frequency = {};
arr.forEach(num => {
frequency[num] = (frequency[num] || 0) + 1;
});
// Further operations using the frequency map
}
const arr = [4, 2, 5, 1, 3, 2];
solve(arr);#include <stdio.h>
#include <stdlib.h>
void solve(int arr[], int n) {
int hashTableSize = 100; // Adjust size according to problem constraints
int hashTable[hashTableSize];
for (int i = 0; i < hashTableSize; ++i) hashTable[i] = 0;
for (int i = 0; i < n; ++i) {
hashTable[arr[i]]++;
}
// Further operations using the hash table
}
int main() {
int arr[] = {4, 2, 5, 1, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
solve(arr, n);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
static void Solve(int[] arr) {
Dictionary<int, int> map = new Dictionary<int, int>();
foreach (int num in arr) {
if (map.ContainsKey(num)) {
map[num]++;
} else {
map[num] = 1;
}
}
// Further operations using the map
}
static void Main() {
int[] arr = {4, 2, 5, 1, 3, 2};
Solve(arr);
}
}Python's dictionary is used to create a frequency map efficiently, allowing for streamlined operations in subsequent logic steps.
Time Complexity: O(n) for processing list.
Space Complexity: O(k) for the frequency dictionary.
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.
function checkDistances(s: string, distance: number[]): boolean {
const d: number[] = Array(26).fill(0);
const n = s.length;
for (let i = 1; i <= n; ++i) {
const j = s.charCodeAt(i - 1) - 97;
if (d[j] && i - d[j] - 1 !== distance[j]) {
return false;
}
d[j] = i;
}
return true;
}func checkDistances(s string, distance []int) bool {
d := [26]int{}
for i, c := range s {
c -= 'a'
if d[c] > 0 && i-d[c] != distance[c] {
return false
}
d[c] = i + 1
}
return true
}impl Solution {
pub fn check_distances(s: String, distance: Vec<i32>) -> bool {
let n = s.len();
let s = s.as_bytes();
let mut d = [0; 26];
for i in 0..n {
let j = (s[i] - b'a') as usize;
let i = i as i32;
if d[j] > 0 && i - d[j] != distance[j] {
return false;
}
d[j] = i + 1;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Sorting | Time Complexity: O(n log n) for sorting. |
| Approach 2: Using Hash Map | Time Complexity: O(n) for processing list. |
| Array or Hash Table | – |
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 |
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.