Trying to solve this string reduction problem. I hope typing this all out will help me clear my head, because I’ve been up too late tonight and now my thoughts are running together, and I don’t want to sleep until I find a solution.
Basically…
- You give me any string made up of the letters “abc”.
- If I see two distinct, adjacent letters (ex: “ab”, “cb”, “ba”…), I can swap them out for the third, unused letter (“ba” becomes “c”).
- I reduce the string until the above rule doesn’t match.
- I tell you the smallest possible string.
Easy, right? With the word “cab”, I change the “ca” to a “b”, end up with “bb”, and I return the length of that string (2).
But the string “abccccccc” is a different deal. If I decide to go in left-to-right order, the “ab” at the beginning becomes a “c”, and then I’m stuck with a string length of 8.
However, if I skip the “ab” and look at “bc” (the second and third letters in the string), I can reduce that to “a” so my string is now “aacccccc”. Then I reduce the second and third characters again and again until I end up with “aa” (string length of 2).
1: "abccccccc"
2: "aacccccc"
3: "abccccc"
4: "aacccc"
5: "abccc"
6: "aacc"
7: "abc"
8: "aa"
Maybe looking at this string as just a line of text is the wrong way to do it. Suppose the string I’m starting with is a node. If I can reduce that string in x different ways, I have x paths I can take from that node. A path ends with a node that I can’t reduce.
That means I start with some string, and then I reduce it in every possible way until I can’t reduce anymore. Once all my paths have ended with nodes, I grab those ending nodes and look at their string lengths. The smallest node is the most-reduced string, so I return its length.
"cab" => "bb" => 2
=> "cc" => 2 Return 2
So basically, I need to write a function that reduces a string at a given point. If I get “cab” and say I want to reduce at “0”, meaning that the 0th and 1st characters in the string (“c” and “a” as “ca”) can be reduced, I can return “bb”.
This is actually for some online contest type deal, and I don’t want to give away too much of what I’m doing. I already know how I’m going to compare my results and continue reducing, but I think once I have this at-point-reduction function written I’ll be golden.
