LeetCode Daily Problem P1625: Lexicographically Smallest String After Operations

---

Timeline

Timeline

2025-10-19

init

BFS

---

Problem:

P1625 Lexicographically Smallest String After Operations

https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/description/?envType=daily-question&envId=2025-10-19

DFS enumeration:

#include <string>
#include <unordered_set>
#include <algorithm>
#include <queue>

using std::string;
using std::unordered_set;
using std::queue;

class Solution {
private:
	void sadd(string &s, int a)
	{
		int i, n;
		n = s.size();
		for (i = 1; i < n; i += 2) {
			s[i] = ((s[i] - '0') + a) % 10 + '0';
		}
	}

	void sshift(string &s, int b)
	{
		int n = s.size();
		b = b % n;

		string substr = s.substr(n - b, b);

		s.erase(s.end() - b, s.end());
		s.insert(s.begin(), substr.begin(), substr.end());
	}

public:
	string findLexSmallestString(string s, int a, int b)
	{
		unordered_set<string> visited;
		queue<string> q;
		string res = s, cur, t;

		q.push(s);
		visited.insert(s);
                // BFS
		while (!q.empty()) {
			cur = q.front();
			q.pop();
			res = min(res, cur);
                        // Two branches: add or rotate

			// Add operation
			t = cur;
			sadd(t, a);
			if (!visited.count(t)) {
				visited.insert(t);
				q.push(t);
			}

			// Rotate operation
			t = cur;
			sshift(t, b);
			if (!visited.count(t)) {
				visited.insert(t);
				q.push(t);
			}
		}

		return res;
	}
};