Longest Subsequence Repeated k Times - Practice Coding Problems

Longest Subsequence Repeated k Times - Problem

String Backtracking Greedy Counting Enumeration Hard

You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

A subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.

For example, "bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "bababcba".

Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.

Input & Output

Example 1 — Basic Case

$ Input: s = "letsleetcode", k = 2

› Output: "let"

💡 Note: The subsequence "let" can be repeated 2 times to form "letlet", which is a subsequence of "letsleetcode". This is the longest such subsequence.

Example 2 — No Valid Subsequence

$ Input: s = "bb", k = 3

› Output: ""

💡 Note: No character appears 3 or more times, so no subsequence can be repeated 3 times.

Example 3 — Single Character

$ Input: s = "ab", k = 1

› Output: "b"

💡 Note: When k=1, we want the lexicographically largest subsequence, which is "b".

Constraints

2 ≤ s.length ≤ 2000
2 ≤ k ≤ 2000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and repetition count k

Process

Find subsequence that when repeated k times is still a subsequence

Output

Longest valid subsequence (lexicographically largest if tie)

Key Takeaway

🎯 Key Insight: Only characters appearing ≥ k times can be part of a valid subsequence

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is that a character must appear at least k times to be part of any valid subsequence. Best approach uses backtracking with frequency-based pruning to build subsequences systematically while avoiding impossible branches. Time: O(n × 2ᵛ × k), Space: O(n + v)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(2ⁿ × n × k)	O(n)	Generate all possible subsequences and check if each can be repeated k times
Frequency Count with Validation	O(n + 2ᵛ × n × k)	O(n + v)	Count character frequencies first, then build valid subsequences incrementally
Optimized Backtracking	O(n × 2ᵛ × k)	O(n + v)	Use backtracking to build subsequences character by character with pruning

Brute Force Enumeration — Algorithm Steps

Step 1: Generate all possible subsequences using bit manipulation
Step 2: For each subsequence, create the k-times concatenated version
Step 3: Check if the concatenated string is a subsequence of original string
Step 4: Keep track of longest valid subsequence (lexicographically largest if tie)

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible subsequences

Concatenate

Repeat each subsequence k times

Validate

Check if concatenated string is subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isSubsequence(const char* target, const char* s) {
    int i = 0;
    int targetLen = strlen(target);
    int sLen = strlen(s);
    
    for (int j = 0; j < sLen && i < targetLen; j++) {
        if (s[j] == target[i]) {
            i++;
        }
    }
    return i == targetLen;
}

char* solution(char* s, int k) {
    int n = strlen(s);
    char* best = malloc(n + 1);
    best[0] = '\0';
    
    // Generate all possible subsequences using bit manipulation
    for (int mask = 1; mask < (1 << n); mask++) {
        char subseq[n + 1];
        int idx = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[idx++] = s[i];
            }
        }
        subseq[idx] = '\0';
        
        // Create k-times concatenated string
        char* target = malloc(idx * k + 1);
        target[0] = '\0';
        for (int i = 0; i < k; i++) {
            strcat(target, subseq);
        }
        
        // Check if target is subsequence of s
        if (isSubsequence(target, s)) {
            if (strlen(subseq) > strlen(best) || 
                (strlen(subseq) == strlen(best) && strcmp(subseq, best) > 0)) {
                strcpy(best, subseq);
            }
        }
        free(target);
    }
    
    return best;
}

int main() {
    char s[1000];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(s, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n × k)

Generate 2^n subsequences, each taking O(n×k) time to validate

✓ Linear Growth

Space Complexity

O(n)

Store current subsequence and concatenated string

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

487 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler