Minimum Distance (DSA Interview Preparation Problems and Solutions) ~ Multiplex Coder

Problem Description

Given a string A which contains only three characters {'x', 'o', '.'}.

Find minimum possible distance between any pair of 'x' and 'o' in the string.

Distance is defined as the absolute difference between the index of 'x' and 'o'.

NOTE: If there is no such pair return -1.

Problem Constraints

1 <= |A| <= 105

Input Format

First and only argument is a string A.

Output Format

Return an integer denoting the minimum possible distance.

Example Input

Input 1:

 A = "x...o.x...o"

Input 2:

 A = "xxx...xxx"

Example Output

Output 1:

Output 2:

-1

Example Explanation

Explanation 1:

 Minimum distance is between 'o' at index 5 and 'x' at index 7 i.e |7 - 5| = 2

Explanation 2:

 There is no such pair, return -1.

Code:

int Solution::solve(string A) {
    int n = A.size();
    int prex[n], sufx[n];
    for(int i = 0; i < n; i++){
        if(A[i] == 'x'){
            prex[i] = i;
        }
        else{
            if(i == 0){
                prex[i] = -1;
            }
            else{
              prex[i] = prex[i-1];
            }
        }
    }
    for(int i = n-1; i >= 0; i--){
        if(A[i] == 'x'){
            sufx[i] = i;
        }
        else{
            if(i == n-1){
                sufx[i] = -1;
            }
            else{
                sufx[i] = sufx[i+1];
            }
        }
    }
    int ans = 1e7;
    for(int i = 0; i < n; i++){
        if(A[i] == 'o'){
            if(prex[i] != -1)
                ans = min(ans, i - prex[i]);
            if(sufx[i] != -1)
                ans = min(ans, sufx[i] - i);
        }
    }
    if(ans == 1e7){
        return -1;
    }
    return ans;
}

Minimum Distance (DSA Interview Preparation Problems and Solutions)

Related Post