Blog

I solved this one yesterday, and want to explain the intuition that I found without looking at the solution. I did have a look at the topics but that was all. I think one good way to learn DSA is to look at the topic of the problem and then solve it without peaking at the solutions. Only if stuck for an hour or more should you look at the solution. I usually try to minimise even the amount of the solution I go through.

The following is a video description I found, which describes it really well. If you prefer reading, see below.

Intuition: BFS

I first tried using DFS here. But I think BFS is the one to use. We need to explore the whole valid graph of this problem.

You can think of many problems as problems in their own space and with states. A graph is a concept to visualise the possible states of a problem. We can go through all the states in the graph which can be denoted as nodes and their connections, the ways we can get from one state to the next. These connections are also called edges.

With a practical problem such as this one, it is important to visualise what the nodes and edges of this problem are. We can then traverse the graph with, for example, a BFS (Breadth First Search), and find the best solution/state (node) of this graph.

For this problem we need to find the node (string) with the best (smallest) value. Lexicographically means we need to find the string that would be found first in a dictionary. So, for example 0001 is before 0002, or 1999 is before 2000. It is good to think of edge cases, that are easy to reason about, with any type of problem. This also teaches you to write unit tests that are better than your LLM can generate. It can be quite challenging to find a minimum set of edge cases for testing.

There are at least 2 approaches to implement BFS. With any graph or tree algorithm like this one, there is a recursive and iterative way to implement it. The recursive way can be more intuitive if you understand recursion well. But the iterative way is more efficient because you do not need to use the callstack to store the current state.

I will detail here the iterative way, because with BFS it is reasonably intuitive.

We need to find the structure, understand and memorise how to implement it in code. It is worth the effort to understand the algorithm and also why it works. This makes recall of it much more intuitive.

I will use C++ here, but you can use any language you prefer.

string findLexSmallestString(
    string s,
    int a, int b
  ) {
  queue<string> q;
  q.push(s);
  while (!q.empty()){
    auto cur=q.front();
    q.pop();
    if(weWantToGoFurther){
      q.push(childState1);
      q.push(childState2);
      // ...
      q.push(childStateN);
    }
  }
  // return ...;
}

There is a pattern here that you can use for any graph or problem traversal.

In particular, in this problem, you want to only traverse 2 child states and only if you have not seen them yet. You can abstract them and name them add(a) and rotate(b)respectively. These are the operations to get to the next states (nodes) in the problem graph. You can optimise them in O(1) but not further. I did it like this:

class Solution {
  string add(
    string s,
    int a
  ){
    string ans;
    for(int i=0;i<s.length();i++){
      if(i%2==0) ans+=s[i];
      else{
        char c=((s[i]-'0')+a)%10+'0';
        ans+=c;
      }
    }
    return ans;
  }
  string rot(string s, int b){
    string ans;
    for(int i=0;i<s.length();++i){
      ans+=s[(i+b)%s.length()];
    }
    return ans;
  }
  public:
  string findLexSmallestString(
    string s, int a, int b
  ) {
    queue<string> q;
    string best=s;
    q.push(s);
    unordered_set<string> seen;
    while (!q.empty()){
      auto cur=q.front();
      q.pop();
      if(cur<best){
        best=cur;
      }
      if(seen.find(cur)==seen.end()){
        q.push(add(cur,a));
        q.push(rot(cur,b));
      }
      seen.insert(cur);
    }
    return best;
  }
};