[Java-알고리즘] Split a String in Balanced Strings

[Problem]

Balanced strings are those who have equal quantity of 'L' and 'R' characters. Given a balanced string s split it in the maximum amount of balanced strings. Return the maximum amount of splitted balanced strings.

[Example1]

Input: s = "RLRRLLRLRL"
Output: 4

Explanation: s can be split into "RL", "RRLL", "RL", "RL", 
each substring contains same number of 'L' and 'R'.

 

[Example2]

Input: s = "RLLLLRRRLR"
Output: 3

Explanation: s can be split into "RL", "LLLRRR", "LR", 
each substring contains same number of 'L' and 'R'.

[Example3]

Input: s = "LLLLRRRR"
Output: 1

Explanation: s can be split into "LLLLRRRR".

 

[Constraint]

• 1 <= s.length <= 1000
• s[i] = 'L' or 'R'

 

[Solution]

class Solution {
    public int balancedStringSplit(String s) {
        char[] characters = s.toCharArray();
        int strLen = s.length();
        int matchCounter = 0;
        int numOfBalanceString = 0;

        for(int i = 0; i< strLen; i++){
            if(characters[i] == 'L'){
                matchCounter++;
            }else{
                matchCounter--;
            }

            if(matchCounter == 0){
                numOfBalanceString++;
            }
        }
        
        return numOfBalanceString;
    }
}

 

 

 

균형잡힌 문자열 문제는 꽤 자주 나오는 문제이다. 여러 변형 문제도 많다. 이전에 풀었던 균형잡힌 문자열 문제는 재귀함수를 구현해서 풀었어야하는 문제였는데 이번 문제는 그럴 필요까진 없었다. 단순히 갯수만 맞으면 균형잡힌 문자열로 판별했으므로 간단한 플래그성 변수를 통해 문자열의 갯수를 파악했다.