fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.Arrays;
  4. import java.util.List;
  5. import java.util.Scanner;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	private static final List<Character> COLORS = Arrays.asList('R', 'G', 'B');
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13. 		 Scanner sc = new Scanner(System.in);
  14.         int n = sc.nextInt();
  15.         sc.nextLine();
  16.         String s = sc.nextLine();
  17.  
  18.         Integer[][] dp = new Integer[n][3];
  19.         for (Integer[] row : dp) {
  20.             Arrays.fill(row, -1);
  21.         }
  22.  
  23.         dp[0][COLORS.indexOf(s.charAt(0))] = 0;
  24.  
  25.         int minMovesToDiversify = findMinMovesToDiversifyGarland(n, s, 1, s.charAt(0), dp);
  26.         System.out.println(minMovesToDiversify);
  27.  
  28. //        for (Integer[] row : dp) {
  29. //            System.out.println("row is " + Arrays.toString(row));
  30. //        }
  31. 	}
  32.  
  33. 	private static int findMinMovesToDiversifyGarland(int n, String s, int currentPos, char prevChar, Integer[][] dp) {
  34.         if (currentPos == n) {
  35.             return 0;
  36.         }
  37.  
  38.         if (s.charAt(currentPos) == prevChar) {
  39.             int minValue = Integer.MAX_VALUE;
  40.             for (int i = 0; i < COLORS.size(); i++) {
  41.                 if (COLORS.get(i) != s.charAt(currentPos)) {
  42.                     minValue = Math.min(minValue, dp[currentPos][COLORS.indexOf(COLORS.get(i))] = 1 + findMinMovesToDiversifyGarland(n, s, currentPos + 1, COLORS.get(i), dp));
  43.                 }
  44.             }
  45. //             dp[currentPos][COLORS.indexOf(s.charAt(currentPos))] =
  46.             return minValue;
  47.         } else {
  48.             return dp[currentPos][COLORS.indexOf(s.charAt(currentPos))] = findMinMovesToDiversifyGarland(n, s, currentPos + 1, s.charAt(currentPos), dp);
  49.         }
  50.     }
  51. }
Success #stdin #stdout 0.1s 49944KB
comments (?)
stdin
copy 
13
BBRRRRGGGGGRR
stdout
copy 
6
https://ideone.com/uwrlIO
language:
Java (HotSpot 12)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!