Leetcode - 1221. Split a String in Balanced Strings

문제

L과 R로만 구성된 문자열이 주어진다. L와 R의 갯수가 동일한 문자열이 balanced한 문자열이라고 할때, 주어진 문자열을 쪼갰을때 모든 문자열이 Balanced되는 경우의수 중 최대 갯수는?

Input: s = "RLRRLLRLRL"
Output: 4
(RL, RRLL, RL, RL)

해결

최대로 쪼개는 갯수이니, 앞부터 가장 작은 문자열이 밸런스가 맞으면 retcnt++, 따라서 greedy 로 해결이가능.

1. Constraints
 - input size: 1~1000
 - return max number - type: int value
 - input s is a balanced itself.
 
2. Ideas
 - brute force - split all kind of combination. 
 - using hashtable? - 
 - greedy, count minimun balanced substring during iteration -> O(N)
 
3. Test Cases
 - assert(func("LR") == 1)
 - assert(func("LRLR") == 2)
 - assert(func("LLLRRR") == 1)
 - assert(func("LRRRLL") == 1)
 - assert(func("RLRRLLRLRL") == 4)

int balancedStringSplit(char * s){
    int ssize = strlen(s);
    int rcnt = 0;
    int lcnt = 0;
    int retcnt = 0;
    
    for (int i = 0; i < ssize; i++) {
        if (s[i] == 'R') rcnt++;
        else if (s[i] == 'L') lcnt++;
        if (rcnt == lcnt) {
            retcnt++;
            rcnt = lcnt = 0;
        }
    }
    return retcnt;
}