Problem Link - Chef and String in Greedy Algorithms
Problem Statement:
There are N students standing in a row and numbered 1 through N from left to right. You are given a string S with length N, where for each valid i, the i-th character of S is ‘x’ if the i-th student is a girl or ‘y’ if this student is a boy. Students standing next to each other in the row are friends.
The students are asked to form pairs for a dance competition. Each pair must consist of a boy and a girl. Two students can only form a pair if they are friends. Each student can only be part of at most one pair. What is the maximum number of pairs that can be formed?
Approach:
- Traverse the string from left to right, checking adjacent characters.
- If the current character is different from the previous one (
s[i] != s[i-1]), it indicates a potential pair, so you increment the counter and skip to the next character.
Complexity:
- Time Complexity:
O(N)Iterate through the whole string as all the pairs are considered. - Space Complexity:
O(1)No extra space is needed to store the result.