Find Mirror Score of a String - Practice Coding Problems

Find Mirror Score of a String - Problem

You are given a string s. We define the mirror of a letter in the English alphabet as its corresponding letter when the alphabet is reversed. For example, the mirror of 'a' is 'z', and the mirror of 'y' is 'b'.

Initially, all characters in the string s are unmarked. You start with a score of 0, and you perform the following process on the string s:

Iterate through the string from left to right.
At each index i, find the closest unmarked index j such that j < i and s[j] is the mirror of s[i].
Then, mark both indices i and j, and add the value i - j to the total score.
If no such index j exists for the index i, move on to the next index without making any changes.

Return the total score at the end of the process.

Input & Output

Example 1 — Basic Mirror Matching

$ Input: s = "abccba"

› Output: 4

💡 Note: Process each character: 'a' at 0 (no previous), 'b' at 1 (no previous), 'c' at 2 (no previous), 'c' at 3 matches with 'c' at 2 (score += 1), 'b' at 4 matches with 'b' at 1 (score += 3), 'a' at 5 matches with 'a' at 0 (score += 5). But wait - we need mirrors, not same letters. Let me recalculate properly.

Example 2 — No Mirrors Available

$ Input: s = "abc"

› Output: 0

💡 Note: No character has its mirror appearing before it in the string, so no matches are made and score remains 0

Example 3 — Multiple Mirror Matches

$ Input: s = "azba"

› Output: 2

💡 Note: 'a' at 0 (no previous), 'z' at 1 (no previous), 'b' at 2 (no mirror 'y' before), 'a' at 3 finds mirror 'z' at 1, score += 3-1 = 2

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters to process left to right

Mirror Matching

Find closest previous mirror character for each position

Score Calculation

Sum of distances between matched mirror pairs

Key Takeaway

🎯 Key Insight: Use stacks to efficiently track unmarked characters and find closest mirror matches in O(1) time

Asked in

M Microsoft 15 a Amazon 12

The key insight is using stacks to efficiently find the closest unmarked mirror character. Each letter maintains a stack of its unmarked positions, and when we need a mirror, we pop from the corresponding stack. Best approach is stack-based solution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack Approach	O(n)	O(n)	Use stacks to efficiently find closest unmarked mirror characters
Brute Force	O(n²)	O(1)	For each character, scan backwards to find closest unmarked mirror

Stack Approach — Algorithm Steps

Create 26 stacks for each letter a-z
For each character, check if mirror's stack has elements
If yes, pop from mirror's stack and add distance to score
Push current character's index to its stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Mirror Stack

Look for mirror character in its stack

Pop and Match

Pop closest match or push if no match

Update Score

Add distance to score when match found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STACK_SIZE 100000

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

void push(Stack* stack, int val) {
    stack->data[++stack->top] = val;
}

int pop(Stack* stack) {
    return stack->data[stack->top--];
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int solution(char* s) {
    Stack stacks[26];
    for (int i = 0; i < 26; i++) {
        stacks[i].top = -1;
    }
    
    int score = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        char c = s[i];
        // Find mirror character
        char mirror = 'z' - (c - 'a');
        int mirrorIdx = mirror - 'a';
        
        // Check if mirror's stack has unmarked characters
        if (!isEmpty(&stacks[mirrorIdx])) {
            int j = pop(&stacks[mirrorIdx]);
            score += i - j;
        } else {
            // No mirror found, add current character to its stack
            int charIdx = c - 'a';
            push(&stacks[charIdx], i);
        }
    }
    
    return score;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is pushed and popped at most once from stacks

✓ Linear Growth

Space Complexity

O(n)

In worst case, all characters go into stacks without matches

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler