1625. Lexicographically Smallest String After Applying Operations

UnknownView on LeetCode

Breadth-First Search String

Time: O(n * 10² * n)

Space: O(n * 10²)

Intuition

Find lexicographically smallest string after applying shift/rotate operations. BFS over all reachable strings.

Algorithm

1BFS with a visited set. Start with s. Two operations: rotate (move last char to front) and add (increment even-indexed chars by a mod 10).
2Return minimum string in visited set.

Common Pitfalls

•Total reachable states bounded. BFS explores all. Rotation cycle is at most n states.

1625.cs

// Approach: BFS exploring all reachable strings via add-to-odd-indices and rotate operations.
// Time: O(n * 10² * n) Space: O(n * 10²)

public class Solution
{
    public string FindLexSmallestString(string s, int a, int b)
    {
        // Use BFS to explore all possible string transformations
        Queue<string> queue = new Queue<string>();
        queue.Enqueue(s);

        // Track visited strings to avoid processing duplicates
        HashSet<string> visited = new HashSet<string>();
        visited.Add(s);

        // Initialize the answer with the original string
        string smallestString = s;
        int length = s.Length;

        // BFS to explore all reachable strings
        while (queue.Count > 0)
        {
            string currentString = queue.Dequeue();

            // Update answer if current string is lexicographically smaller
            if (string.Compare(smallestString, currentString, StringComparison.Ordinal) > 0)
                smallestString = currentString;

            // Operation 1: Add 'a' to all odd-indexed digits
            char[] charArray = currentString.ToCharArray();
            for (int i = 1; i < length; i += 2)
                // Add 'a' to digit at odd index and take modulo 10
                charArray[i] = (char)(((charArray[i] - '0' + a) % 10) + '0');
            string additionResult = new string(charArray);

            // Operation 2: Rotate string to the right by 'b' positions
            string rotationResult = currentString.Substring(length - b) + currentString.Substring(0, length - b);

            // Add both transformed strings to queue if not visited
            foreach (string transformedString in new List<string> { additionResult, rotationResult })
            {
                if (visited.Add(transformedString))
                    queue.Enqueue(transformedString);
            }
        }

        return smallestString;
    }
}

Was this solution helpful?