https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/ from JP Morgan

Thinking process: Search problem. We want to find the lexicographically smallest string. So the first idea I had was the brute force approach, which means we need to construct all possible strings. Checked the constrain. Good, the string length is less than 100. Brute force approach seems good to me.

The next question is how do we do the brute force solution. So for each string, we basically have two options, do operation one or operation two. After that, we have a new string, and we have two options again… This looks like a DFS pattern.

We want to stop the search if we have visited the same string before, and we want to find the lexicographically smallest string, so it’s straightforward to use a ordered set to store what string we visited already, and after we explore all of them, we just pick the first one in the set. Below is the code.

 1class Solution {
 2public:
 3    set<string> st;
 4    void dfs(string s, int a, int b) {
 5        if (st.count(s)) return;
 6        st.insert(s);
 7        int N = s.size();
 8        string ns = s.substr(N-b, b) + s.substr(0, N-b);
 9        dfs(ns, a, b);
10        for (int i=1; i<N; i+=2) {
11            s[i] = ((s[i] - '0' + a)%10) + '0';
12        }
13        // cout << s << endl;
14        dfs(s, a, b);
15    }
16    string findLexSmallestString(string s, int a, int b) {
17        dfs(s, a, b);
18        return *st.begin();
19    }
20};