Shortest Distance to a Character Solution Code in C++/Java/Python/JavaScript
Problem
Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.
The distance between two indices i and j is abs(i - j), where abs is the absolute value function.
Example
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
Input: s = "aaab", c = "b"
Output: [3,2,1,0]
Constraints
- 1 <= s.length <= 104
- s[i] and c are lowercase English letters.
- It is guaranteed that c occurs at least once in s.
Figuring out the "Shortest Distance to a Character solution" requires logical thinking. We will be coding the Shortest Distance to a Character solution in brute force as well as try to figure out the optimal approach as well.
Brute Force Approach
Intuition
As the question description says we need to figure out the shortest distance from all the characters to a specific character.
Suppose s="learnyard" and c = "a".
For this example, we could see that the character 'n' at index 4 has one 'a' to the left and one 'a' to the right. We need to choose the distance that is minimum to it.
The first intuitive thought is let's try to find the distance of each character to the character 'a' appearing left and the distance of each character to the character 'a' appearing to their right.
Then it would be easy for us to analyse which is the minimum of the two distances.
Approach
Initialize Variables: Get the length of the input string s (n).
Create three integer arrays:
- leftDist[n] to store distances from the left.
- rightDist[n] to store distances from the right.
- res[n] to store the final result.
Fill leftDist and rightDist with n (a large value).
Left-to-Right Pass (Tracking Closest 'c' from the Left):
Initialize dist = n (a large value).
Traverse s from left to right (i = 0 to n-1):
- If s[i] == c, reset dist = 0.
- Store dist in leftDist[i].
- Increment dist for the next iteration.
Right-to-Left Pass (Tracking Closest 'c' from the Right):
Reinitialize dist = n.
Traverse s from right to left (i = n-1 to 0):
- If s[i] == c, reset dist = 0.
- Store dist in rightDist[i].
- Increment dist for the next iteration.
Compute Final Result: For each index i, store res[i] = min(leftDist[i], rightDist[i]).
Return res array as the final output.
Dry-Run
Input:- s="learnyard" and c = "a"
Output:- [2,1,0,1,2,1,0,1,2]
Step 1: Initialize Variables
- n = 9 (length of string s).
- Create three arrays:
- leftDist = [9, 9, 9, 9, 9, 9, 9, 9, 9] (initially filled with n).
- rightDist = [9, 9, 9, 9, 9, 9, 9, 9, 9] (initially filled with n).
- res = [0, 0, 0, 0, 0, 0, 0, 0, 0] (final result).
- Initialize dist = 9 (a large value).
Step 2: Left-to-Right Pass
- Start iterating from i = 0 to i = 8.
- If s[i] == 'a', reset dist = 0. Otherwise, store dist in leftDist[i] and increment dist.
- After this pass:
- leftDist[0] = 9 because 'l' is not 'a'.
- leftDist[1] = 9 because 'e' is not 'a'.
- leftDist[2] = 0 because 'a' is found, reset dist.
- leftDist[3] = 1 because 'r' is one position away from the last 'a'.
- leftDist[4] = 2 because 'n' is two positions away.
- leftDist[5] = 3 because 'y' is three positions away.
- leftDist[6] = 0 because another 'a' is found, reset dist.
- leftDist[7] = 1 because 'r' is one position away.
- leftDist[8] = 2 because 'd' is two positions away.
Step 3: Right-to-Left Pass
- Start iterating from i = 8 to i = 0.
- If s[i] == 'a', reset dist = 0. Otherwise, store dist in rightDist[i] and increment dist.
- After this pass:
- rightDist[8] = 9 because 'd' is far from 'a'.
- rightDist[7] = 9 because 'r' is far from 'a'.
- rightDist[6] = 0 because 'a' is found, reset dist.
- rightDist[5] = 1 because 'y' is one position away.
- rightDist[4] = 2 because 'n' is two positions away.
- rightDist[3] = 3 because 'r' is three positions away.
- rightDist[2] = 0 because another 'a' is found, reset dist.
- rightDist[1] = 1 because 'e' is one position away.
- rightDist[0] = 2 because 'l' is two positions away.
Step 4: Compute Final Result
- For each index i, take the minimum of leftDist[i] and rightDist[i] to compute res[i].
- res[0] = min(9, 2) = 2.
- res[1] = min(9, 1) = 1.
- res[2] = min(0, 0) = 0.
- res[3] = min(1, 3) = 1.
- res[4] = min(2, 2) = 2.
- res[5] = min(3, 1) = 1.
- res[6] = min(0, 0) = 0.
- res[7] = min(1, 9) = 1.
- res[8] = min(2, 9) = 2.
Final Output
✅ Result: [2, 1, 0, 1, 2, 1, 0, 1, 2]
Shortest Distance to a Character Solution
Now, let's checkout the Shortest Distance to a Character solution in c++, Java, Python and JavaScript
"Shortest Distance to a Character" Code in all Languages.
1. Lexicographically Smallest Palindrome solution in C++ Try on Compiler
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> shortestToChar(string s, char c) {
int n = s.length();
// Array to store distance from the left occurrence of 'c'
vector<int> leftDist(n, n);
// Array to store distance from the right occurrence of 'c'
vector<int> rightDist(n, n);
// Result array to store the final minimum distances
vector<int> res(n, 0);
// Initialize distance with a large value
int dist = n;
// Traverse from left to right
for (int i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s[i] == c)
dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (int i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s[i] == c)
dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (int i = 0; i < n; i++)
res[i] = min(leftDist[i], rightDist[i]);
return res;
}
int main() {
string s;
char c;
// Taking input for the string
cout << "Enter the string: ";
cin >> s;
// Taking input for the target character
cout << "Enter the character: ";
cin >> c;
// Calling the function
vector<int> result = shortestToChar(s, c);
// Printing the result
cout << "Shortest distances: ";
for (int num : result)
cout << num << " ";
cout << endl;
return 0;
}
2. Shortest Distance to a Character in Java Try on Compiler
import java.util.Arrays;
import java.util.Scanner;
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
// Array to store distance from the left occurrence of 'c'
int[] leftDist = new int[n];
// Array to store distance from the right occurrence of 'c'
int[] rightDist = new int[n];
// Result array to store the final minimum distances
int[] res = new int[n];
// Initialize both leftDist and rightDist with a large value (n)
Arrays.fill(leftDist, n);
Arrays.fill(rightDist, n);
// Initialize distance with a large value
int dist = n;
// Traverse from left to right
for (int i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s.charAt(i) == c)
dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (int i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s.charAt(i) == c)
dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (int i = 0; i < n; i++)
res[i] = Math.min(leftDist[i], rightDist[i]);
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Taking input for the string
System.out.print("Enter the string: ");
String s = scanner.next();
// Taking input for the target character
System.out.print("Enter the character: ");
char c = scanner.next().charAt(0);
// Creating object and calling the function
Solution sol = new Solution();
int[] result = sol.shortestToChar(s, c);
// Printing the result
System.out.println("Shortest distances: " + Arrays.toString(result));
scanner.close();
}
}
3. Shortest Distance to a Character Solution in Python Try on Compiler
def shortest_to_char(s: str, c: str):
n = len(s)
# Array to store distance from the left occurrence of 'c'
left_dist = [n] * n
# Array to store distance from the right occurrence of 'c'
right_dist = [n] * n
# Result list to store the final minimum distances
res = [0] * n
# Initialize distance with a large value
dist = n
# Traverse from left to right
for i in range(n):
# If current character is 'c', reset distance
if s[i] == c:
dist = 0
# Store the distance from the left occurrence of 'c'
left_dist[i] = dist
# Increment distance as we move right
dist += 1
# Reinitialize distance with a large value
dist = n
# Traverse from right to left
for i in range(n - 1, -1, -1):
# If current character is 'c', reset distance
if s[i] == c:
dist = 0
# Store the distance from the right occurrence of 'c'
right_dist[i] = dist
# Increment distance as we move left
dist += 1
# Compute the minimum distance for each index
for i in range(n):
res[i] = min(left_dist[i], right_dist[i])
return res
if __name__ == "__main__":
# Taking input from the user
s = input("Enter the string: ")
c = input("Enter the character: ")[0]
# Calling the function
result = shortest_to_char(s, c)
# Printing the result
print("Shortest distances:", result)
4. Shortest Distance to a Character solution in JavaScript Try on Compiler
const fs = require("fs");
// Read input from a file
const input = fs.readFileSync("input.txt", "utf8").trim().split("\n");
// Extract string and character from input
const s = input[0].trim();
const c = input[1].trim()[0];
function shortestToChar(s, c) {
let n = s.length;
// Array to store distance from the left occurrence of 'c'
let leftDist = new Array(n).fill(n);
// Array to store distance from the right occurrence of 'c'
let rightDist = new Array(n).fill(n);
// Result array to store the final minimum distances
let res = new Array(n);
// Initialize distance with a large value
let dist = n;
// Traverse from left to right
for (let i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s[i] === c) dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (let i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s[i] === c) dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (let i = 0; i < n; i++) {
res[i] = Math.min(leftDist[i], rightDist[i]);
}
return res;
}
// Call the function and print the result
console.log("Shortest distances:", shortestToChar(s, c).join(" "));
Shortest Distance to a Character Complexity Analysis
Time Complexity: O(n)
First Pass (Left to Right)
- The loop runs from 0 to n-1, performing O(1) operations per iteration.
- Time Complexity: O(n).
Second Pass (Right to Left)
- The loop runs from n-1 to 0, performing O(1) operations per iteration.
- Time Complexity: O(n).
Final Pass (Computing Result)
- Another loop runs from 0 to n-1, performing O(1) operations per iteration.
- Time Complexity: O(n).
Total Time Complexity
- Since each pass runs in O(n) time, and we have three passes, the total time complexity remains: O(n)+O(n)+O(n)=O(n)
- Final Time Complexity: O(n).
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
- leftDist and rightDist arrays each take O(n) space.
- The res array also takes O(n) space.
- The integer variable dist takes O(1) space.
- The only extra auxiliary space used apart from the input and output is leftDist and rightDist arrays.
Thus, Auxiliary Space Complexity: O(n).
Total Space Complexity
The total space includes:
Input String s: Given as input, so not counted in extra space.
Output Array res: Necessary for returning the result (O(n)).
Additional Arrays (leftDist and rightDist): Each of size O(n).
- The total space used is O(n) + O(n) + O(n) = O(n).
- Final Total Space Complexity: O(n).
The Brute force approach used a lot of extra space to calculate the result. But, in order to move further in the interview process we need to figure out the best solution in terms of both time and space.
Optimal Approach
Intuition
To understand the space optimal approach, let's think of a scenerio. Imagine you're standing in a long line of houses on a street. Some houses have ice cream shops 🍦, and you love ice cream! Your goal is to find out how far each house is from the nearest ice cream shop.
For example, if we have houses labeled as:
loveleetcode
loveleetcode
↑ ↑ ↑ ↑
Now, for each house, you want to know the shortest distance to the closest ice cream shop. We will use two runners (pointers), called Left Runner and Right Runner .
First Runner (Left to Right) → The Left Runner starts from the leftmost house and moves to the right. If it finds an ice cream shop , it marks 0 for that house. Then, as it moves forward, it counts how far it is from the last ice cream shop.
Second Runner (Right to Left) ← The Right Runner starts from the rightmost house and moves to the left. It does the same thing, counting how far it is from the closest ice cream shop . But this time, it corrects any mistakes made by the Left Runner, making sure we get the closest distance.
For each house, we pick the minimum distance from both runners.
In the above approach we used two array to store the distances from left and right respectively and then finalised the minimum of them to store it in the resultant array. This time we will be handling all the operations in a single array.
Let's now see the Algorithm
Shortest Distance to a Character Algorithm
- We start by finding the length of the string and creating an array to store the result.
- We use two pointers, left and right, to track positions while scanning the string.
- We move the right pointer from left to right, searching for occurrences of character c.
- If it's the first occurrence, we update all previous positions with increasing distances.
- Otherwise, we fill the distances symmetrically between the last and current occurrence of c.
- We update the left pointer to the current right position whenever we find c.
- After the first pass, we check if there are remaining positions to the right of the last c, and we update them accordingly.
- Finally, we return the result array, which contains the shortest distances to the nearest occurrence of c.
Let's now see the Shortest Distance to a Character Approach.
Approach
Initialize variables:
- Determine the length of the string s.
- Create an integer array result of the same length to store distances.
- Initialize two pointers: left = 0 and right = 0.
First pass (Left to Right traversal):
- Move the right pointer from the beginning to the end of the string.
- When right finds the target character c:
- If it's the first occurrence of c, update all previous positions with increasing distances.
- Otherwise, update distances symmetrically between left and right.
- Update left to the current right position.
Second pass (Right to Left traversal):
- After the first pass, check if there are remaining positions to the right of the last occurrence of c.
- If so, update them with increasing distances.
Return the result array containing the shortest distances for each character in s.
Let us understand this with a video,
shortest-distance-to-a-character-optimal animation
Dry-Run
Input:- s="learnyard" and c = "a"
Output:- [2,1,0,1,2,1,0,1,2]
Step 1: Initialization
- length = 9 (since "learnyard" has 9 characters).
- result = [0, 0, 0, 0, 0, 0, 0, 0, 0] (array of size 9).
- left = 0, right = 0.
Step 2: First While Loop (Right Moves →)
We move right from index 0 to 8, checking for occurrences of 'a'.
Iteration 1: right = 0, s[0] = 'l'
- Not 'a', so move right to 1.
Iteration 2: right = 1, s[1] = 'e'
- Not 'a', so move right to 2.
Iteration 3: right = 2, s[2] = 'a' (First Occurrence of 'a')
- Since left == 0 and s[left] != 'a', update all values before index 2.
- Set temp = 2, then update:
result = [2, 1, 0, 0, 0, 0, 0, 0, 0]
- Update left = 2.
- Move right to 3.
Iteration 4: right = 3, s[3] = 'r'
- Not 'a', move right to 4.
Iteration 5: right = 4, s[4] = 'n'
- Not 'a', move right to 5.
Iteration 6: right = 5, s[5] = 'y'
- Not 'a', move right to 6.
Iteration 7: right = 6, s[6] = 'a' (Second Occurrence of 'a')
- Perform symmetric update between left = 2 and right = 6:
result = [2, 1, 0, 1, 2, 1, 0, 0, 0]
- Update left = 6.
- Move right to 7.
Iteration 8: right = 7, s[7] = 'r'
- Not 'a', move right to 8.
Iteration 9: right = 8, s[8] = 'd'
- Not 'a', move right to 9 (exit loop).
Step 3: Final Update (Rightmost Distances)
Since left = 6, update remaining distances from index 7 onward:
result = [2, 1, 0, 1, 2, 1, 0, 1, 2]
Final Output: [2, 1, 0, 1, 2, 1, 0, 1, 2]
Shortest Distance to a Character Solution
Now, let's checkout the Shortest Distance to a Character solution in c++, Java, Python and JavaScript
"Shortest Distance to a Character" Code in all Languages.
1. Lexicographically Smallest Palindrome solution in C++ Try on Compiler
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> shortestToChar(string s, char c) {
int n = s.length();
// Array to store distance from the left occurrence of 'c'
vector<int> leftDist(n, n);
// Array to store distance from the right occurrence of 'c'
vector<int> rightDist(n, n);
// Result array to store the final minimum distances
vector<int> res(n, 0);
// Initialize distance with a large value
int dist = n;
// Traverse from left to right
for (int i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s[i] == c)
dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (int i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s[i] == c)
dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (int i = 0; i < n; i++)
res[i] = min(leftDist[i], rightDist[i]);
return res;
}
int main() {
string s;
char c;
// Taking input for the string
cout << "Enter the string: ";
cin >> s;
// Taking input for the target character
cout << "Enter the character: ";
cin >> c;
// Calling the function
vector<int> result = shortestToChar(s, c);
// Printing the result
cout << "Shortest distances: ";
for (int num : result)
cout << num << " ";
cout << endl;
return 0;
}
2. Shortest Distance to a Character in Java Try on Compiler
import java.util.Arrays;
import java.util.Scanner;
class Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
// Array to store distance from the left occurrence of 'c'
int[] leftDist = new int[n];
// Array to store distance from the right occurrence of 'c'
int[] rightDist = new int[n];
// Result array to store the final minimum distances
int[] res = new int[n];
// Initialize both leftDist and rightDist with a large value (n)
Arrays.fill(leftDist, n);
Arrays.fill(rightDist, n);
// Initialize distance with a large value
int dist = n;
// Traverse from left to right
for (int i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s.charAt(i) == c)
dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (int i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s.charAt(i) == c)
dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (int i = 0; i < n; i++)
res[i] = Math.min(leftDist[i], rightDist[i]);
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Taking input for the string
System.out.print("Enter the string: ");
String s = scanner.next();
// Taking input for the target character
System.out.print("Enter the character: ");
char c = scanner.next().charAt(0);
// Creating object and calling the function
Solution sol = new Solution();
int[] result = sol.shortestToChar(s, c);
// Printing the result
System.out.println("Shortest distances: " + Arrays.toString(result));
scanner.close();
}
}
3. Shortest Distance to a Character Solution in Python Try on Compiler
def shortest_to_char(s: str, c: str):
n = len(s)
# Array to store distance from the left occurrence of 'c'
left_dist = [n] * n
# Array to store distance from the right occurrence of 'c'
right_dist = [n] * n
# Result list to store the final minimum distances
res = [0] * n
# Initialize distance with a large value
dist = n
# Traverse from left to right
for i in range(n):
# If current character is 'c', reset distance
if s[i] == c:
dist = 0
# Store the distance from the left occurrence of 'c'
left_dist[i] = dist
# Increment distance as we move right
dist += 1
# Reinitialize distance with a large value
dist = n
# Traverse from right to left
for i in range(n - 1, -1, -1):
# If current character is 'c', reset distance
if s[i] == c:
dist = 0
# Store the distance from the right occurrence of 'c'
right_dist[i] = dist
# Increment distance as we move left
dist += 1
# Compute the minimum distance for each index
for i in range(n):
res[i] = min(left_dist[i], right_dist[i])
return res
if __name__ == "__main__":
# Taking input from the user
s = input("Enter the string: ")
c = input("Enter the character: ")[0]
# Calling the function
result = shortest_to_char(s, c)
# Printing the result
print("Shortest distances:", result)
4. Shortest Distance to a Character solution in JavaScript Try on Compiler
const fs = require("fs");
// Read input from a file
const input = fs.readFileSync("input.txt", "utf8").trim().split("\n");
// Extract string and character from input
const s = input[0].trim();
const c = input[1].trim()[0];
function shortestToChar(s, c) {
let n = s.length;
// Array to store distance from the left occurrence of 'c'
let leftDist = new Array(n).fill(n);
// Array to store distance from the right occurrence of 'c'
let rightDist = new Array(n).fill(n);
// Result array to store the final minimum distances
let res = new Array(n);
// Initialize distance with a large value
let dist = n;
// Traverse from left to right
for (let i = 0; i < n; i++) {
// If current character is 'c', reset distance
if (s[i] === c) dist = 0;
// Store the distance from the left occurrence of 'c'
leftDist[i] = dist;
// Increment distance as we move right
dist++;
}
// Reinitialize distance with a large value
dist = n;
// Traverse from right to left
for (let i = n - 1; i >= 0; i--) {
// If current character is 'c', reset distance
if (s[i] === c) dist = 0;
// Store the distance from the right occurrence of 'c'
rightDist[i] = dist;
// Increment distance as we move left
dist++;
}
// Compute the minimum distance for each index
for (let i = 0; i < n; i++) {
res[i] = Math.min(leftDist[i], rightDist[i]);
}
return res;
}
// Call the function and print the result
console.log("Shortest distances:", shortestToChar(s, c).join(" "));
Shortest Distance to a Character Complexity Analysis
Time Complexity: O(n)
First while loop (right iteration across s)
The while (right < length) loop runs O(n) times.
Inside the loop, if s.charAt(right) == c, different operations happen:
- Case 1 (Filling distances from the left to the first c): Runs O(d), where d is the distance to the first c.
- Case 2 (Filling between two c characters using two pointers): Runs O(d), where d is the distance between two consecutive c characters.
Each leftPointer and rightPointer meet in the middle, leading to an O(n) contribution over all iterations.
Final for loop (Handling the last segment after the last c)
This runs a single loop from left + 1 to length - 1, iterating at most O(n) times.
Total Time Complexity
- The while loop runs O(n), and all inner operations contribute at most O(n).
- The final for loop runs O(n).
- The total time complexity remains O(n).
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
The algorithm only uses:
- int left, right, temp, leftPointer, rightPointer, leftDistance, rightDistance, distance: O(1) space.
- The result array is necessary to return the output (O(n)), but it's not considered auxiliary space.
Thus, Auxiliary Space Complexity: O(1).
Total Space Complexity
The total space includes:
- Output array (result): O(n).
- Constant auxiliary variables: O(1).
Thus, Total Space Complexity: O(n).
Similar Problems
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.