Random Walking Assets

a blog of software engineer, dreamer and daddy

Beads

| Comments

Problem: here

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
 ID: chinux1
 PROG: beads
 LANG: C++11
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int countBeadsBackward(string necklace, int index)
{
    if (index > 0) {
        char firstColor = necklace[index-1];

        int i = index - 1;
        while (i > 0 && (firstColor == necklace[i] || necklace[i] == 'w' || firstColor == 'w')) {
            // first Color may be 'w', if so, we need to update
            if (firstColor == 'w' && necklace[i] != 'w') {
                firstColor = necklace[i];
            }
            i--;
        }
        return index - 1 - i;
    } else {
        return 0;
    }
}

int countBeadsForward(string necklace, int index)
{
    if (index < necklace.size()) {
        char firstColor = necklace[index];

        int i = index;
        while (i < necklace.size() && (firstColor == necklace[i] || necklace[i] == 'w' || firstColor == 'w')) {
            // first Color may be 'w', if so, we need to update
            if (firstColor == 'w' && necklace[i] != 'w') {
                firstColor = necklace[i];
            }
            i++;
        }
        return i - index;
    } else {
        return 0;
    }
}

int countBeads(string necklace, int index)
{
    return countBeadsBackward(necklace, index) + countBeadsForward(necklace, index);
}

int maxNumberOfBeads(string doubleNecklace)
{
    int maxBeads = 0;
    for (int i = 1; i < doubleNecklace.length(); i++) {
        int num = countBeads(doubleNecklace, i);
        if (num > maxBeads){
            maxBeads = num;
        }
    }
    return maxBeads;
}

int main() {
    ofstream fout ("beads.out");
    ifstream fin ("beads.in");

    // Line 1
    int N = 0;
    fin >> N;

    // Line 2
    string necklace;
    fin >> necklace;

    string doubleNecklace = necklace + necklace;

    fout << min(maxNumberOfBeads(doubleNecklace), N) << endl;

    return 0;
}

Comments