Leetcode 2399: Check Distances Between Same Letters Solution

Here, we will help to understand about how to solve Check Distances Between Same Letters Solution of leet code 2399 with code and algorithm.

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: str = "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

2)
Input: str = "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.

Check Distances Between Same Letters code in C++

Code 1:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool checkDistances(string s, vector<int>& distance) {
    vector<int> pos(26, -1); 
    
    for (int i = 0; i < s.size(); ++i) {
        int k = s[i] - 'a';
        
        if (pos[k] == -1) {
            pos[k] = i; 
        }
        else if (i - pos[k] != distance[k] + 1) {
            return false;
        } 
    }
    return true; 
}
    
using namespace std;

int main()
{
    string str = "abaccb";
    vector<int> 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};
    
    cout<<checkDistances(str, distance);

    return 0;
}

Code 2:

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

bool checkDistances(string s, vector<int>& distance) {
    map<char, int> m;
        
    for(int i = 0; i < s.length(); i++) {
        if(m.find(s[i]) == m.end()) {
            m[s[i]] = i;
        } else {
            m[s[i]] = i - m[s[i]] - 1;
                
            if(distance[s[i] - 'a'] != m[s[i]]) {
                return false;
            }
        }
    }
    return true;
}
    
using namespace std;

int main()
{
    string str = "abaccb";
    vector<int> 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};
    
    cout<<checkDistances(str, distance);

    return 0;
}

Output:

true

To check more leetcode problem’s solution. Pls click given below link:

https://www.techieindoor.com/category/leetcode/