使最长字符间隔等于K所需的最少操作

Question

在比赛中有人问我这个问题。给定仅包含M和L的字符串，我们可以将任何“ M”更改为“ L”或将任何“ L”更改为“ M”。该函数的目的是计算为了达到所需的最长M间隔长度K

而必须进行的最少更改。例如，给定S =“ MLMMLLM”并且K = 3，该函数应返回1。我们可以更改位置4的字母（从0开始计数）以获得“ MLMMMLM”，其中字母“ M”的最长间隔恰好是三个字符长。

再举一个例子，给定S =“ MLMMMLMMMM”和K = 2，该函数应返回2。例如，我们可以修改位置2和7处的字母，以获得满足所需属性的字符串“ MLLMMLMLMM”。

这是我到目前为止尝试过的方法，但是我没有得到正确的输出：我遍历字符串，并且只要最长的字符数超过K，就用L代替M。

public static int solution(String S, int K) {

    StringBuilder Str = new StringBuilder(S);

    int longest=0;int minCount=0;

    for(int i=0;i<Str.length();i++){

        char curr=S.charAt(i);

        if(curr=='M'){

            longest=longest+1;

        if(longest>K){

           Str.setCharAt(i, 'L');

           minCount=minCount+1;

           }

        }

        if(curr=='L')

         longest=0;

 }

  if(longest < K){

        longest=0;int indexoflongest=0;minCount=0;

        for(int i=0;i<Str.length();i++){

            char curr=S.charAt(i);

            if(curr=='M'){

            longest=longest+1;

            indexoflongest=i;

            }

            if(curr=='L')

              longest=0;

        }

        Str.setCharAt(indexoflongest, 'M');

        minCount=minCount+1;

    }

  return minCount;

}

Answer 1

&nbsp;intprocess_data(const char *m, int k){&nbsp; &nbsp; int m_cnt = 0, c_cnt = 0;&nbsp; &nbsp; char ch;&nbsp; &nbsp; const char *st = m;&nbsp; &nbsp; int inc_cnt = -1;&nbsp; &nbsp; int dec_cnt = -1;&nbsp; &nbsp; while((ch = *m++) != 0) {&nbsp; &nbsp; &nbsp; &nbsp; if (m_cnt++ < k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt += ch == 'M' ? 0 : 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((m_cnt == k) && (&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (inc_cnt == -1) || (inc_cnt > c_cnt))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; inc_cnt = c_cnt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else if (ch == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (*st++ == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* losing & gaining M carries no change provided&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* there is atleast one L in the chunk. (c_cnt != 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* Else it implies stretch of Ms&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c_cnt <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int t;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* compute min inserts needed to brak the&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* stretch to meet max of k.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t = (k - c_cnt) / (k+1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dec_cnt += t;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ASSERT(c_cnt > 0, "expect c_cnt(%d) > 0", c_cnt);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ASSERT(inc_cnt != -1, "expect inc_cnt(%d) != -1", inc_cnt);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* Losing L and gaining M */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (--c_cnt < inc_cnt) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; inc_cnt = c_cnt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c_cnt <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* take this as a first break and restart&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* as any further addition of M should not&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* happen. Ignore this L&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; st = m;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m_cnt = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (*st++ == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* losing m & gaining l */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // losing & gaining L; no change&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return dec_cnt != -1 ? dec_cnt : inc_cnt;}

Answer 2

更正的代码：intprocess_data(const char *m, int k){&nbsp; &nbsp; int m_cnt = 0, c_cnt = 0;&nbsp; &nbsp; char ch;&nbsp; &nbsp; const char *st = m;&nbsp; &nbsp; int inc_cnt = -1;&nbsp; &nbsp; int dec_cnt = -1;&nbsp; &nbsp; while((ch = *m++) != 0) {&nbsp; &nbsp; &nbsp; &nbsp; if (m_cnt++ < k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt += ch == 'M' ? 0 : 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((m_cnt == k) && (&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (inc_cnt == -1) || (inc_cnt > c_cnt))) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; inc_cnt = c_cnt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else if (ch == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (*st++ == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* losing & gaining M carries no change provided&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* there is atleast one L in the chunk. (c_cnt != 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* Else it implies stretch of Ms&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c_cnt <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ASSERT(c_cnt > 0, "expect c_cnt(%d) > 0", c_cnt);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ASSERT(inc_cnt != -1, "expect inc_cnt(%d) != -1", inc_cnt);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* Losing L and gaining M */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (--c_cnt < inc_cnt) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; inc_cnt = c_cnt;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c_cnt <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* compute min inserts needed to brak the&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* stretch to meet max of k.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dec_cnt += (dec_cnt == -1 ? 1 : 0) + ((k - c_cnt) / (k+1));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* take this as a first break and restart&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* as any further addition of M should not&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* happen. Ignore this L&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; st = m;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m_cnt = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (*st++ == 'M') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* losing m & gaining l */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c_cnt++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // losing & gaining L; no change&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if (c_cnt <= 0) {&nbsp; &nbsp; &nbsp; &nbsp; /*&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* compute min inserts needed to brak the&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;* stretch to meet max of k.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; dec_cnt += (dec_cnt == -1 ? 1 : 0) + ((k - c_cnt) / (k+1));&nbsp; &nbsp; }&nbsp; &nbsp; return dec_cnt != -1 ? dec_cnt : inc_cnt;}