Repeated Subsequence - CPP Solution

1. Introduction

This blog post explores a string processing problem that focuses on identifying repeated subsequences within a string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The challenge is to find if there exists a subsequence of length 2 or more that is repeated in the string.

Problem

Given a string, the task is to check whether there is a repeated subsequence in the string that has a length of 2 or more. This problem tests our ability to understand and manipulate sequences and strings.

2. Solution Steps

1. Create a frequency table for all characters in the string.

2. Iterate through the string, checking if we can form a repeated subsequence.

3. A repeated subsequence exists if a character appears at least twice, and there is at least one other character between its occurrences.

4. Return true if such a condition is met; otherwise, return false.

3. Code Program

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Function to check for repeated subsequence
bool hasRepeatedSubsequence(const string& str) {
    vector<int> freq(256, 0); // Frequency table for all ASCII characters

    // Count frequency of each character
    for (char ch : str) {
        freq[ch]++;
    }

    for (int i = 0; i < str.length(); i++) {
        if (freq[str[i]] > 1) {
            // Check for the presence of at least one other character in between
            for (int j = i + 2; j < str.length(); j++) {
                if (str[i] == str[j]) {
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    string s = "XYBAXB";
    cout << "Has Repeated Subsequence: " << (hasRepeatedSubsequence(s) ? "true" : "false") << endl;
    return 0;
}

Output:

Has Repeated Subsequence: true

Explanation:

The function hasRepeatedSubsequence checks for repeated subsequences in a given string. It first creates a frequency table of all characters and then iterates through the string. If it finds a character that appears more than once and has at least one different character between its occurrences, it concludes that a repeated subsequence exists. For instance, in "XYBAXB", it finds 'X' and 'B' as part of a repeated subsequence "XB", hence returns true. In contrast, "ABCA" returns false as it lacks any repeated subsequence.