Leetcode 2399: Check Distances Between Same Letters
You are given a string
s consisting of lowercase English letters where each letter appears exactly twice. You are also given an array distance of length 26, where each element represents the number of characters between the two occurrences of the corresponding letter (0-indexed, ‘a’ corresponds to index 0, ‘b’ to index 1, etc.). Your task is to determine if the string s is a ‘well-spaced’ string. A string is well-spaced if, for each letter in s, the number of characters between its two occurrences matches the corresponding value in the distance array.Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` of length `n` and an array `distance` of size 26, representing the spacing rules for each letter in the alphabet.
Example: s = 'abcdbf', distance = [1, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Constraints:
• 2 <= s.length <= 52
• Each letter appears exactly twice in `s`.
• The `distance` array has length 26.
Output: Return `true` if `s` is a well-spaced string, otherwise return `false`.
Example: Output: true
Constraints:
Goal: The goal is to verify if the string is well-spaced according to the spacing rules defined by the `distance` array.
Steps:
• 1. Iterate through each character in the string `s`.
• 2. For each character, check if the number of characters between its two occurrences matches the value in the `distance` array.
• 3. If for any character, the spacing condition is violated, return `false`.
• 4. If all characters satisfy their spacing conditions, return `true`.
Goal: The problem constraints ensure that the string `s` has a manageable length (2 to 52 characters) and that each character appears exactly twice, making the problem solvable efficiently.
Steps:
• The length of `s` is guaranteed to be even, as each character appears exactly twice.
• The array `distance` has a fixed length of 26, corresponding to the letters 'a' to 'z'.
Assumptions:
• The input string `s` contains only lowercase English letters.
• The array `distance` provides valid values for each letter, where values represent the number of letters between the two occurrences.
• 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]
• Explanation: In this example, the spacing between occurrences of 'a' is 1 (distance[0] = 1), between 'b' is 3 (distance[1] = 3), and 'c' has no spacing (distance[2] = 0). The string meets the well-spaced condition, so the output is true.
• 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]
• Explanation: In this case, 'a' appears at indices 0 and 1, but the distance condition for 'a' (distance[0] = 1) is not satisfied, as there are no letters between them. Therefore, the output is false.
Approach: The approach involves checking the distance between occurrences of each character in the string `s` and ensuring that it satisfies the conditions specified in the `distance` array.
Observations:
• Each character in `s` appears exactly twice, so we only need to check the distance between the two occurrences of each character.
• We can efficiently track the positions of each character in the string and verify if the distance condition holds for each letter.
Steps:
• 1. Create an array `pos` of size 26 to store the position of the first occurrence of each letter.
• 2. Iterate through the string `s`. For each character, check if the distance between its two occurrences matches the corresponding value in `distance`.
• 3. If any character violates the distance condition, return false. Otherwise, return true at the end.
Empty Inputs:
• Although `s` will always have a length of at least 2, it is important to consider cases where `s` contains only one unique character repeated twice.
Large Inputs:
• The problem ensures that `s.length` will not exceed 52, so the solution must efficiently handle this input size.
Special Values:
• When `distance` contains zeros, it signifies that there are no characters between the occurrences of a letter.
Constraints:
• We can safely assume that the constraints guarantee a valid input string `s` and a well-formed `distance` array.
bool checkDistances(string s, vector<int>& distance) {
int pos[26] = {};
for (int i = 0; i < s.size(); ++i) {
int n = s[i] - 'a';
if (pos[n] > 0 && distance[n] != i - pos[n])
return false;
pos[n] = i + 1;
}
return true;
}
1 : FunctionDefinition
bool checkDistances(string s, vector<int>& distance) {
This line defines the function checkDistances, which takes a string 's' and a vector 'distance' as parameters. The function returns a boolean value.
2 : VariableInitialization
int pos[26] = {};
An array 'pos' of size 26 is initialized to zero to keep track of the last seen position of each letter in the string. The array indexes correspond to the letters of the alphabet.
3 : LoopStart
for (int i = 0; i < s.size(); ++i) {
A for loop is started that iterates through each character of the string 's'.
4 : CharacterToIndex
int n = s[i] - 'a';
Each character of the string 's' is converted into an index (0 for 'a', 1 for 'b', etc.) by subtracting 'a' from the character.
5 : ConditionalCheck
if (pos[n] > 0 && distance[n] != i - pos[n])
This condition checks whether the character has appeared before and if the distance between this occurrence and the previous one matches the corresponding value in the 'distance' vector.
6 : ReturnFalse
return false;
If the condition in the previous step is true, the function immediately returns false, indicating that the distances do not match.
7 : UpdatePosition
pos[n] = i + 1;
The position of the current character is updated in the 'pos' array. The index is incremented by 1 to indicate that this character has been seen at the current index.
8 : ReturnTrue
return true;
If no mismatched distances were found during the loop, the function returns true, indicating that the distances between identical characters match the given values.
Best Case: O(n), where n is the length of the string `s`. This is the case when all characters are well-spaced.
Average Case: O(n), where n is the length of the string `s`. We need to check each character's spacing.
Worst Case: O(n), where n is the length of the string `s`. We check every character's distance condition.
Description: The time complexity is linear in terms of the length of `s`, as we perform a single pass through the string.
Best Case: O(1), as space usage is independent of input size.
Worst Case: O(1), as we are using a constant amount of space to track positions of characters.
Description: The space complexity is constant, as we only need a fixed-size array to store the first occurrence of each character.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus