Dynamic Programming O(N) time solution with O(1) space
The intuition is that the minimum number of moves depends on the previous values in the string. \nThe problem can be solved via dynamic programming using the fo
The intuition is that the minimum number of moves depends on the previous values in the string. \nThe problem can be solved via dynamic programming using the following relation.\n\nif current value is \'X\' => then\n`moves[index] = moves[index-3] + 1`\n\nthe reason is that the last three indices will automatically be converted to OOO if we are applying the move at the current index.\n\nIf current value is \'O\' then\n`moves[index] = moves[index-1]`\n\nbecause no move is applied so we copy the last minimum number of moves.\n\nTime Complexity : `O(N)`\nWe do a single pass over the string\n\nSpace Complexity : `O(1)`\nSince we use a circular queue of size 3 we use constant extra space. For a problem with variable length window the space complexity would be `O(W)` where W is the window length.\n\n\n```\nclass Solution {\n    public int minimumMoves(String s) {\n        \n        // circular queue for keeping track of the minimum moves for the past three moves\n        int[] moves = new int[3];\n        \n        int len = s.length();\n        \n        for (int index = 0; index < len; index++) {\n            \n            // index to update in the circular queue \n            int id = index % moves.length;\n            \n            // moves[index-3] + 1\n            if (s.charAt(index) == \'X\') {\n                moves[id]++;\n            } else {\n                moves[id] = moves[ (index+2) % moves.length];// moves[index-1]\n            }\n        }\n        \n        return moves[ ( s.length()-1) % moves.length];// return the minimum moves for the last index\n    }\n}\n```
[]