title: Length of smallest string with three-letter alphabet achievable by replacing two adjacent different characters with the third
body: <p>This is an interview problem that I am stuck on:</p>
  
  <blockquote>
    <p>Given a string consisting of a, b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character.  For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?</p>
  </blockquote>
  
  <p>My attempted solution:</p>
  
  <pre><code>import java.io.BufferedReader;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.LinkedList;
  import java.util.List;
  
  public class Solution {
      public static void main(String[] args) {
          try {
              BufferedReader in = new BufferedReader(new InputStreamReader(
                      System.in));
  
              System.out.println(solve(in.readLine()));
  
              in.close();
          } catch (FileNotFoundException e) {
              e.printStackTrace();
          } catch (IOException e) {
              e.printStackTrace();
          }
      }
  
      private static int solve(String testCase) {
          LinkedList&lt;String&gt; temp = new LinkedList&lt;String&gt;(deconstruct(testCase));
  
          for (int i = 0; i &lt; (temp.size() - 1); i++) {
              if (!temp.get(i).equals(temp.get(i + 1))) {
                  temp.add(i, getThirdChar(temp.remove(), temp.remove()));
                  i = -1;
              }
          }
  
          return reconstruct(temp).length();
      }
  
      private static List&lt;String&gt; deconstruct(String testCase) {
          List&lt;String&gt; temp = new LinkedList&lt;String&gt;();
  
          for (int i = 0; i &lt; testCase.length(); i++) {
              temp.add(testCase.charAt(i) + "");
          }
  
          return temp;
      }
  
      private static String reconstruct(List&lt;String&gt; temp) {
          String testCase = "";
  
          for (int i = 0; i &lt; temp.size(); i++) {
              testCase += temp.get(i);
          }
  
          return testCase;
      }
  
      private static String getThirdChar(String firstChar, String secondChar) {
          return "abc".replaceAll("[" + firstChar + secondChar + "]+", "");
      }
  }
  </code></pre>
  
  <p>The code seems to work fine on test inputs "cab" (prints "2"), "bcab" (prints "1"), and "ccccc" (prints "5").  But I keep getting told that my code is wrong.  Can anyone help me figure out where the bug is?</p>