Skip to content

All into one loop

This technique is commonly used to minimize the complexity of nested loops. Usually helpful when dealing with max, min values in a string or an array.

Be greedy with your memory resources, only save variables and arrays when you'll use them, in other words, think of there's a way to minimize the number of for loops into only one for loop

Example1: given a string, return the size of the longest substring of equal chars in it.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    int conChar(string s) {
        int countMax = 1, count = 1;

        // Pass through each char of s
        for (int i = 0; i < s.size()-1; i++) {

            // If you find two consecutives chars equal, start counting
            if (s[i] == s[i+1]) {
                count++;

                // * Set countMax to whatever number bigger than him
                countMax = max(countMax, count);
            }

            // Reset the counter whenever the chars differ
            else count = 1;
        }
        return countMax;
    }

With time and practice these solutions become typical.

Problems

  1. Longest increasing subsequence
  2. Flipped 01 .
  3. Set records .
  4. Maximal contiguous sum.

See also