Medium level problem leetcode (Hiring Contest Microsoft)

Small buckle out of fall camp, on the way to collect some leaves and yellow leaves, he leaves the initial use of these put together a collection Akiba leaves , the string leaves contains only lowercase characters r and y which characters r represent one leaves, the characters y represent a yellow leaves.
For the sake of beauty and neatness, Xiaokou wanted to adjust the arrangement of leaves in the collection into three parts: red, yellow, and red. The number of leaves in each part may not be equal, but they must be greater than or equal to 1. For each adjustment operation, the small buckle can replace a red leaf with a yellow leaf or replace a yellow leaf with a red leaf. May I ask how many adjustment operations are required for Xiaokou at least to adjust the Autumn Leaves Collection.

Example 1:

enter: leaves = "rrryyyrryyyrr"

Output: 2

Explanation: Adjust twice, replace the two red leaves in the middle with yellow leaves, and get “rrryyyyyyyyrr”

Example 2:

enter: leaves = "ryr"

Output: 0

Explanation: The requirements have been met, no additional operations are required


  • 3 <= leaves.length <= 10^5
  • leaves It contains only characters 'r' and character 'y'

My thought process
Just transverse the array using two pointers and tranverse array again to make side ways red and middle one yellow

But this process is O(n^3)

Note :- Please use Google translater for this.
question needed to reduce the TC.
Any thought process??


1 Like