\n\nI encountered a question in Google online assessment , it seems to be a variation of LIS.\n\nA smart string is one with characters in strictly increasing or decreasing order. Given a string M, we need to determine the minimum number of contiguous substrings in which M can be broken so that each substring is smart.\n\nExamples: Input: abcdcba \nOutput: 2 \n\npartitioned into abc and dcba\n\nInput: ffdhbbbdeeggbb \nOutput:4\n\nI thought of creating 2 auxillary dp arrays that store length of longest increasing substrings and longest decreasing substrings till a particular index. I am getting stuck in cases resembling the resembling the second example mentioned above. In this case the substrings can be: fd, hb, bde, eg, gb But the result is 4 because cut was made at gb so eg automatically got cut. How to take this into account?\n

\n\nI encountered a question in Google online assessment , it seems to be a variation of LIS.\n\nA smart string is one with characters in strictly increasing or