Go: package main

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

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)

map<char, int> m;
map<string, int> ans;

int main() {

	m['r'] = 1;
	m['g'] = 2;
	m['b'] = 4;
	
	string str;
	while (cin >> str, str != "0") {
		
		queue<pair<int, string> > que;
		que.push(make_pair(0, str));
		
		while (!que.empty()) {
			int t = que.front().first;
			string now = que.front().second;
			que.pop();
			
			if (ans.find(now) != ans.end()) continue;
			ans[now] = t;
			
			REP(i, now.size() - 1) {
				if (now[i] != now[i + 1]) {
					string next = now;
					int nextcor = 7 - m[now[i]] - m[now[i + 1]];
					switch (nextcor) {
					case 1: next[i] = next[i + 1] = 'r'; break;
					case 2: next[i] = next[i + 1] = 'g'; break;
					case 4: next[i] = next[i + 1] = 'b'; break;
					}
					que.push(make_pair(t + 1, next));
				}
			}
		}
		char c[3] = {'r', 'g', 'b'};
		string ser[3] = {};
		REP(i, 3) REP(j, str.size()) {
			ser[i] += c[i];
		}
		int miner = INF;
		REP(i, 3) if (ans.find(ser[i]) != ans.end()) miner = min(miner, ans[ser[i]]);
		if (miner == INF) puts("NA");
		else cout << miner << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

bool check(string s){
    for(int i=0; i< s.size()-1; i++) if(s[i] != s[i+1]) return false;
    return true;
}

vector<string> v;

bool emergence(string s){
    for(int i=0; i< v.size(); i++) if(v[i] == s) return true;
    else return false;
}

int main(){
    string s;
    while(cin >> s, s!= "0"){
        queue<pair<string, int> > que;
        que.push(make_pair(s, 0));
        int ret = 9;
        while(que.size()){
            s = que.front().first; int count = que.front().second; que.pop();

            if(ret < count) continue;
            if(check(s))ret = count;
            if(emergence(s)) continue;
            else v.push_back(s);

            for(int i=0; i< s.size()-1; i++){
                if(s[i] != s[i+1]){
                    string t = s.substr(i, 2);
                    sort(t.begin(),t.end());
                    if(t == "br") t = "gg";
                    else if(t == "bg") t = "rr";
                    else if(t == "gr") t = "bb";
                    que.push(make_pair(s.substr(0, i)+t+s.substr(i+2), count+1));
                }
            }
        }
        if(ret == 9) cout << "NA" << endl;
        else cout << ret << endl;
    }
}

C++: #include <iostream>
#include <string>
#include <queue>
using namespace std;
queue<int> q;
int t[59049];
int INF=100000;
int encode(vector<int> vc){
	int p=0;
	for(int i=0;i<vc.size();i++){
		p=p*3+vc[i];
	}
	return p;
}
vector<int> decode(int p,int n){
	vector<int> vc(n);
	for(int i=0;i<n;i++){
		vc[n-i-1]=p%3;
		p/=3;
	}
	return vc;
}
int main(){
	while(true){
		for(int i=0;i<59049;i++) t[i]=INF;
		string s;
		cin >> s;
		if(s=="0") break;
		int n=s.size(),start=0,goal=1;
		for(int i=0;i<n;i++) goal*=3;
		goal-=1;
		for(int i=0;i<n;i++){
			if(s[i]=='r') start=start*3+2;
			if(s[i]=='g') start=start*3+1;
			if(s[i]=='b') start=start*3;
		}
		q.push(start);
		t[start]=0;
		int ok=-1;
		while(q.size()){
			int p=q.front();
			if(p==0 || p==goal/2 || p==goal){
				ok=p;
				while(q.size()) q.pop(); 
				break;
			}
			q.pop();
			vector<int> vc=decode(p,n);
			for(int i=0;i<n-1;i++){
				if(vc[i]==vc[i+1]) continue;
				vector<int> vc_c=vc;
				vc_c[i]=vc_c[i+1]=((vc[i]+vc[i+1])*2)%3;
				int hoge=encode(vc_c);
				if(t[hoge]!=INF) continue;
				q.push(hoge);
				t[hoge]=t[p]+1;
			}
		}
		if(ok==-1) cout << "NA" << endl;
		else cout << t[ok] << endl;
	}
	return 0;
}