educative.io

Why use if if statement in the for loop instead of using while loop in the for loop?

Courses
,
#1

Hi @Design_Gurus,

I don’t understand why there is if statement in the for loop instead of using while loop in the for loop.

I found another solution online below which uses while loop in the for loop.
And I think array has better performance than map for this question. Any thoughts? Thank you!

    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0, maxCount = 0, maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
1 Like
#2

Hi @Franklin,

We don’t need the ‘while’ loop, only an ‘if’ condition is sufficient because the ‘if’ (or ‘while’) condition will only be true once. In other words, if you have a ‘while’ loop, it will execute only once.

The condition end - start + 1 - maxCount > k will turn false as soon as we make start++.

A fixed array will always have better performance, but it fixes you for a specific set of letters like in the above case 26 chars for English; which will be sufficient for an interview.

Hope this clarifies your question.

1 Like
#3

Hi @Design_Gurus,

I think the maxCount might be changed if the maxCount char is in the start position.
in this case, this should be executed more than one time. How do you think about it?
Thank you.

1 Like
#4 
import java.util.*;

class CharacterReplacement {
  public static int findLength(String str, int k) {
    int windowStart = 0, maxLength = 0, maxRepeatLetterCount = 0;
    Map<Character, Integer> letterFrequencyMap = new HashMap<>();
    // try to extend the range [windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      letterFrequencyMap.put(rightChar, letterFrequencyMap.getOrDefault(rightChar, 0) + 1);
      maxRepeatLetterCount = Math.max(maxRepeatLetterCount, letterFrequencyMap.get(rightChar));

      while (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
        char leftChar = str.charAt(windowStart);
        letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
        maxRepeatLetterCount = getMaxcharfreq(letterFrequencyMap);
        windowStart++;
      }

      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
  }

  // I added this helper method to avoid the changing of maxRepeatLetterCount due to windowStart' moving.
  private static int getMaxcharfreq(Map<Character, Integer> charfreq) {
      int maxcharfreq = 0;
      for (char curfreq : charfreq.keySet()) {
          maxcharfreq = Math.max(maxcharfreq, charfreq.get(curfreq));
      }
      return maxcharfreq;
  }

  public static void main(String[] args) {
    System.out.println(CharacterReplacement.findLength("aabccbb", 2));
    System.out.println(CharacterReplacement.findLength("abbcb", 1));
    System.out.println(CharacterReplacement.findLength("abccde", 1));
  }
}

@Design_Gurus
Based on your code, I modified the solution. I will very appreciate if I can hear your opinions.

#5

@Joybee, can you give a real example where you thing the ‘while’ loop runs more than one time?

#6

@Design_Gurus
Eventually, that can give the correct answer for this kind of question. But during the process, the window could have more than 4 types of character and maxRepeatLetterCount also will be a mess.

In the below case( str = [a a b c d e], k = 2), at 5 round, it will jump into if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) , start will be 0 -> 1.
Because the leftChar is a, a also will be removed from the window, current maxRepeatLetterCount obviously should be 1, but if use if, the maxRepeatLetterCount is still 2. So I think here need to use while and re-calculate the maxRepeatLetterCount to give the correct maxRepeatLetterCount.

1. 
  start
  ↓
  [a] a b c d e
    ↑
    end
- hashMap = [a->1]
- maxRepeatLetterCount = 1
- condition: 
 (windowEnd - windowStart + 1 - maxRepeatLetterCount) > k
  0         -     0       + 1 -       1               = 0
- maxLength = 1

2. 
  [a a] b c d e
- hashMap = [a->2]
- maxRepeatLetterCount = 2
- condition: 
 (windowEnd - windowStart + 1 - maxRepeatLetterCount) > k
  1         -     0       + 1 -       2               = 0
- maxLength = 2

3. 
  [a a b] c d e
- hashMap = [a->2, b->1]
- maxRepeatLetterCount = 2
- condition: 
 (windowEnd - windowStart + 1 - maxRepeatLetterCount) > k
  2         -     0       + 1 -       2               = 1
- maxLength = 3

4. 
  [a a b c] d e
- hashMap = [a->2, b->1, c->1]
- maxRepeatLetterCount = 2
- condition: 
 (windowEnd - windowStart + 1 - maxRepeatLetterCount) > k
  3         -     0       + 1 -       2               = 2
- maxLength = 4

5. 
  [a a b c d] e
- hashMap = [a->2, b->1, c->1, d->1]
- maxRepeatLetterCount = 2 (<- a)
- condition: 
 (windowEnd - windowStart + 1 - maxRepeatLetterCount) > k
  4         -     0       + 1 -       2               = 3 > k
  
  - leftChar: a
    hashMap = [a->1, b->1, c->1, d->1]
    windowStart = 1    ===>   a [a b c d] e
    maxRepeatLetterCount = 1 (because `a` has been removed)
- maxLength = 4
#7

You got the maxRepeatLetterCount wrong. It is a global count for any repeating letter in any valid window and NOT only the current window. In our code, we are not recalculating the maxRepeatLetterCount in the ‘if’ condition. It works, because although the current window might have more different elements than required but it does not matter as we will eventually kick them out.

Also, if the total number characters are not fixed, your algorithm’s time complexity is O(n^2) because of the helper function getMaxcharfreq.

1 Like