White Wall
Source: codechef
Difficulty: 1475

White Wall
Toofan loves white walls! He recently painted a wall with some colors:
Red (R)
,
Green (G)
, and
Blue (B)
. However, he realized that the wall doesn't look as bright and white as he imagined.
Toofan's wall has length$N$, meaning it has$N$positions placed in a line, and each position can be painted in one color — either red, blue, or green.
You are given a string$S$of length$N$, denoting the initial coloring of the wall.
A
white wall
is defined as a wall where
every consecutive set of positions with length divisible by$3$contains equal numbers of R, G, and B
.
Formally, for
every
pair of indices$(L, R)$such that$1 \leq L \leq R \leq N$and$(R-L+1)$is divisible by$3$, there must be an equal amount of
R
,
G
, and
B
in the substring$S_LS_{L+1}S_{L+2}\ldots S_R$.
For instance,$S =$RGBR
is an example of a white wall - the only substrings with length divisible by$3$are
RGB
(with$L = 1$and$R = 3$) and
GBR
($L = 2$and$R = 4$), which both have an equal number of each color.$S =$RGBRGG
is an example of a wall that's not white: choosing$L = 1$and$R = 6$gives us a segment with length$6$(which is a multiple of$3$), which has three positions painted green but only one painted blue, which aren't equal.
Toofan can repaint a single position on the wall to any other color (
R
,
G
, or
B
) in one operation.
Your task is to determine the
minimum number of operations
required to transform the given wall into a white wall.
Input Format
The first line contains a single integer$T$— the number of test cases.
Each test case consists of two lines of input.
The first line contains an integer$N$— the length of the wall.
The second line contains a string$S$of length$N$, where each character is either
R
,
G
, or
B
, denoting the initial coloring of the wall.
Output Format
For each test case, print a single integer — the minimum number of operations needed to make the wall white.
Constraints$1 \leq T \leq 10^5$$3 \leq N \leq 3 \times 10^5$$S_i \in \{R, G, B\}$for all$1 \leq i \leq N$It is guaranteed that the sum of all$N$across all test cases does not exceed$3\times 10^5$.
Sample 1:
Explanation:
Test case$1$:
Initial coloring:
RGBRGG
This is not a white wall: as noted in the statement, choosing$L = 1$and$R = 6$gives us a substring of length$6$with different numbers of red/blue/green parts.
Paint the$6$-th position to
B
, to make the wall
RGBRGB
.
This can be verified to be a white wall.
The pairs$(L, R)$that must be checked are:$(1, 3), (2, 4), (3, 5), (4, 6), (1, 6)$.
Total changes:$1$.
Test case$2$:
Initial coloring:
RRR
Paint the$2$-nd position to
G
, and the$3$-rd block to
B
, to obtain
RGB
.
Total changes:$2$.
It can be proved that less than$2$changes cannot result in a white wall.

Sample Input:
2
6
RGBRGG
3
RRR

Sample Output:
1
2

C++ solution:
#include <bits/stdc++.h>
using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define forn(i, n) forsn(i, 0, n)
#define dforn(i, n) dforsn(i, 0, n)

#define pb push_back
#define pf push_front
#define mp make_pair
#define fst first
#define snd second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())

typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int R[3] = {0,0,0},G[3] = {0,0,0},B[3] = {0,0,0};
        for(int j = 0; j < 3; j++)
        {
            for(int i = 0 + j; i < n; i+=3)
            {
                if(s[i] == 'R')
                {
                    R[j]++;
                }
                else if(s[i] == 'G')
                {
                    G[j]++;
                }
                else if(s[i] == 'B')
                {
                    B[j]++;
                }
            }
        }
        int res = n;
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    if(i != j && j != k && i != k)
                    {
                        res = min(res, n - R[i] - G[j] - B[k]);
                    }
                }
            } 
        }
        
        cout << res << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
)

var dinoPatterns = []string{"RGB", "RBG", "GRB", "GBR", "BRG", "BGR"}

func minDinoOperationsToWhiteWall(n int, dinoStr string) int {
    minDinoChanges := n

    for _, dinoPattern := range dinoPatterns {
        dinoChanges := 0
        for i := 0; i < n; i++ {
            if dinoStr[i] != dinoPattern[i%3] {
                dinoChanges++
            }
        }
        if dinoChanges < minDinoChanges {
            minDinoChanges = dinoChanges
        }
    }

    return minDinoChanges
}

func main() {
    dinoReader := bufio.NewReader(os.Stdin)
    dinoWriter := bufio.NewWriter(os.Stdout)
    defer dinoWriter.Flush()

    var t int
    fmt.Fscan(dinoReader, &t)

    for t > 0 {
        t--
        var n int
        var dinoStr string
        fmt.Fscan(dinoReader, &n, &dinoStr)

        fmt.Fprintln(dinoWriter, minDinoOperationsToWhiteWall(n, dinoStr))
    }
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), n, i, minChange, count;
            String possibilities[] = {"RGB", "RBG", "GBR", "GRB", "BRG", "BGR"};
            StringBuilder sb = new StringBuilder();
  
            while(__ -- > 0) {
                n = nextInt();
                next(sb);
                minChange = n;
                
                for(var possibility : possibilities) {
                    count = 0;
                    for (i = 0; i < n; i++) {
                        if (sb.charAt(i) != possibility.charAt(i % 3)) count++;
                    }
                    
                    if (minChange > count) minChange = count;
                }
                
                outData.append(minChange).append('\n');
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
// your code goes here
function MIN_OPE(N, S) {
    const pat = ["RGB", "RBG", "GRB", "GBR", "BRG", "BGR"];
    let min_charge = Infinity;
    for (const pattern of pat) {
        let changes = 0;
        for (let i = 0; i < N; i++) {
            if (S[i] !== pattern[i % 3]) {
                changes++;
            }
        }
        min_charge = Math.min(min_charge, changes);
    }
    return min_charge;
}

function processInput(input) {
    const input_data = input.trim().split("\n");
    const T = parseInt(input_data[0], 10);
    let res = [];
    
    for (let i = 1; i < input_data.length; i += 2) {
        const N = parseInt(input_data[i], 10);
        const S = input_data[i + 1];
        res.push(MIN_OPE(N, S));
    }
    
    console.log(res.join("\n"));
}

// Fast input handling
process.stdin.resume();
process.stdin.setEncoding("utf-8");
let inputinput_data = "";
process.stdin.on("data", (chunk) => {
    inputinput_data += chunk;
});
process.stdin.on("end", () => {
    processInput(inputinput_data);
});

Python solution:
# cook your dish here
import sys

def main():
    import threading
    def solve():
        T = int(sys.stdin.readline())
        permutations = [
            ['R', 'G', 'B'],
            ['R', 'B', 'G'],
            ['G', 'R', 'B'],
            ['G', 'B', 'R'],
            ['B', 'R', 'G'],
            ['B', 'G', 'R']
        ]

        for _ in range(T):
            N = int(sys.stdin.readline())
            S = sys.stdin.readline().strip()
            min_repaints = N

            for perm in permutations:
                repaints = 0
                for i in range(N):
                    expected_color = perm[i % 3]
                    if S[i] != expected_color:
                        repaints += 1
                if repaints < min_repaints:
                    min_repaints = repaints

            print(min_repaints)

    threading.Thread(target=solve).start()

if __name__ == "__main__":
    main()

Ruby solution:
def main
  input = $stdin.read.split("\n")
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  permutations = [
    %w[R G B],
    %w[R B G],
    %w[G R B],
    %w[G B R],
    %w[B R G],
    %w[B G R]
  ]

  t.times do
    n = input[ptr].to_i
    ptr += 1
    s = input[ptr].chars
    ptr += 1
    min_repaints = n

    permutations.each do |perm|
      repaints = 0
      (0...n).each do |i|
        expected_color = perm[i % 3]
        repaints += 1 unless s[i] == expected_color
      end
      min_repaints = repaints if repaints < min_repaints
    end

    puts min_repaints
  end
end

main