XYSTRP - Editorial

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.