algoadvance

Leetcode 2900. Longest Unequal Adjacent Groups Subsequence I

Problem Statement

Given a string s consisting of lowercase English letters, the task is to find out the length of the longest subsequence where no two adjacent characters are the same. Note that the characters in the subsequence must appear in the same order as in the given string s.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of string s?
    • Are there any specific characters we need to consider or just lowercase English letters?
  2. Output:
    • Are we only interested in the length of the longest subsequence, or do we also need to return the subsequence itself?

Let’s proceed with these assumptions for input constraints for now:

Strategy

To solve this problem, we can employ a simple greedy approach:

  1. Traverse the string and build the longest subsequence by checking each character and ensuring that it is not the same as the last added character to the subsequence.
  2. Keep count of the length of this subsequence as we build it.

Code

Here is the C++ implementation:

#include <iostream>
#include <string>

// Function to calculate the longest unequal adjacent groups subsequence length
int longestUnequalAdjacentSubsequence(const std::string &s) {
    if (s.empty()) return 0;
    
    int maxLength = 1; // Start with the first character, hence length is at least 1
    char lastChar = s[0];
    
    for (size_t i = 1; i < s.length(); ++i) {
        if (s[i] != lastChar) {
            maxLength++;
            lastChar = s[i];
        }
    }

    return maxLength;
}

// Main function for testing
int main() {
    std::string s;
    std::cout << "Enter the string: ";
    std::cin >> s;
    
    int result = longestUnequalAdjacentSubsequence(s);
    std::cout << "The length of the longest unequal adjacent groups subsequence is: " << result << std::endl;
    
    return 0;
}

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the length of the input string s. This is because we traverse the string once and perform constant time operations for each character.

Explanation

  1. Initialization: We start by assuming the subsequence length to be 1 because at a minimum, the subsequence will have at least one character.
  2. Traversal: We iterate through the string from the second character to the end.
  3. Check and Update: For each character, check if it is different from the last character added to the longest subsequence. If it is, increase the length of the subsequence and update the last character.
  4. Result: Finally, return the length of the longest subsequence with no two adjacent characters being the same.

This approach ensures that we capture the longest subsequence while only making a single pass through the string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI