Java | O(N) greedy with explanation how to come up with the greedy idea
Many of us can write the correct greedy strategy. But most discussions don\'t tell how it works and why it works here. If you are interested please read the fol
Many of us can write the correct greedy strategy. But most discussions don\'t tell how it works and why it works here. If you are interested please read the following part:)\n\nHere\'s my explanation:\n1.Because one move have to change three consecutive characters together. Change \'OOO\' is just a waste of opportunities. We can make list of all the possible situations:\n```\n// one X\nOOX  OXO  XOO\n//two X\nXXO  XOX  OXX\n//three X\nXXX\n```\nAnd we define them as basic element here. All the move we will change is those basic elements.\n2.There\'s some identical situations. eg. \n```\n//OOX is identical to XOO and OXO when the sequence is OOXOO\n//XXO is identical to OXX when the sequence is OXXO\n```\n3.Those situations indicates that we can get the same result (remove some X) and move step despite the basic elements are different.\n4.We can find an representative for group of elements and here comes with our greedy strategy: once we find an X, we add one to the steps and move the pointer 3 indexes away.\n\nThe basic idea of greedy strategy is to find the common part of situations so we can detect them using less operations. (Just like the find a dophine use the hump in its head.)\n\n```\nclass Solution {\n    public int minimumMoves(String s) {\n        int i=0;\n        int step=0;\n        while(i<s.length()){\n            if(s.charAt(i)==\'X\'){\n                i=i+3;\n                step++;\n            }\n            else{\n                i++;\n            }\n        }\n        return step;\n    }\n}\n```\nupvote if you really like it.
['Greedy', 'Java']