Lexicographically Smallest String After Applying Operations

Lexicographically Smallest String After Applying Operations - Problem

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.

You can apply either of the following two operations any number of times and in any order on s:

Operation 1: Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".
Operation 2: Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s becomes "6345".

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input & Output

Example 1 — Basic Case

$ Input: s = "5014", a = 9, b = 2

› Output: "0145"

💡 Note: Apply operation 2 to rotate right by 2: "5014" → "1450". Then apply operation 2 again: "1450" → "0145". This gives the lexicographically smallest result.

Example 2 — Only Operation 1 Needed

$ Input: s = "74", a = 5, b = 1

› Output: "24"

💡 Note: Apply operation 1 to add 5 to odd indices: "74" → "72" (7+5=12→2). Continue: "72" → "70" → "78" → "76" → "74" → "72"... Then try rotations to get "24".

Example 3 — No Operations Needed

$ Input: s = "0000", a = 1, b = 1

› Output: "0000"

💡 Note: The string is already lexicographically smallest possible (all zeros), so no operations improve it.

Constraints

2 ≤ s.length ≤ 100
s.length is even
s consists of digits from 0 to 9
1 ≤ a ≤ 9
1 ≤ b ≤ s.length - 1

Visualization

Tap to expand

Understanding the Visualization

Input String

Original string "5014" with operations a=9, b=2

Apply Operations

Operation 1: Add 9 to odd indices, Operation 2: Rotate right by 2

Find Minimum

Explore all reachable states to find "0145"

Key Takeaway

🎯 Key Insight: Use BFS to systematically explore all reachable string states while avoiding cycles with a visited set

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that this is a graph search problem where each string state can transition to new states via two operations. The BFS approach systematically explores all reachable states while using a visited set to avoid cycles. Best approach uses BFS with state tracking: Time: O(10^n), Space: O(10^n) where n is string length.

Common Approaches

Approach	Time	Space	Notes
✓ BFS with State Tracking	O(n × 10^n)	O(10^n)	Use BFS to explore all reachable states systematically
Brute Force with Recursion	O(2^d)	O(d)	Try all possible sequences of operations recursively

BFS with State Tracking — Algorithm Steps

Initialize queue with original string
For each state, apply both operations
Add new states to queue if not visited
Track the minimum string found
Continue until queue is empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with original string in queue

Expand Level

Apply both operations to current level states

Track Minimum

Update minimum string as we discover new states

Code -

solution.c — C

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

#define MAX_STATES 100000

char states[MAX_STATES][1001];
int front = 0, rear = 0;
char visited[MAX_STATES][1001];
int visitedCount = 0;

int isVisited(char* s) {
    for (int i = 0; i < visitedCount; i++) {
        if (strcmp(visited[i], s) == 0) {
            return 1;
        }
    }
    return 0;
}

void addVisited(char* s) {
    strcpy(visited[visitedCount++], s);
}

void applyOp1(char* s, int a, char* result) {
    strcpy(result, s);
    int len = strlen(s);
    for (int i = 1; i < len; i += 2) {
        result[i] = '0' + (s[i] - '0' + a) % 10;
    }
}

void applyOp2(char* s, int b, char* result) {
    int n = strlen(s);
    b = b % n;
    if (b == 0) {
        strcpy(result, s);
        return;
    }
    strncpy(result, s + n - b, b);
    strncpy(result + b, s, n - b);
    result[n] = '\0';
}

char* solution(char* s, int a, int b) {
    char* result = (char*)malloc(1001 * sizeof(char));
    strcpy(result, s);
    
    strcpy(states[rear++], s);
    addVisited(s);
    
    while (front < rear && rear < MAX_STATES && visitedCount < MAX_STATES) {
        char current[1001];
        strcpy(current, states[front++]);
        
        if (strcmp(current, result) < 0) {
            strcpy(result, current);
        }
        
        char op1Result[1001], op2Result[1001];
        applyOp1(current, a, op1Result);
        if (!isVisited(op1Result)) {
            addVisited(op1Result);
            strcpy(states[rear++], op1Result);
        }
        
        applyOp2(current, b, op2Result);
        if (!isVisited(op2Result)) {
            addVisited(op2Result);
            strcpy(states[rear++], op2Result);
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    int a, b;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    scanf("%d", &a);
    scanf("%d", &b);
    
    char* result = solution(s, a, b);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 10^n)

In worst case, can generate up to 10^n different strings of length n

✓ Linear Growth

Space Complexity

O(10^n)

Visited set can store up to 10^n different string states

⚡ Linearithmic Space

24.0K Views

Medium Frequency

~25 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

BFS with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler