Katkat
Back

Check Whether a Word Repeated K Times Is a Subsequence

QuinceSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to optimize string pattern matching by using modular arithmetic and pointer manipulation to avoid unnecessary memory allocation.

Problem Statement

Given a source string S and a target string T, determine if the string formed by concatenating T exactly k times is a subsequence of S. A string A is a subsequence of B if A can be obtained from B by deleting zero or more characters without changing the relative order of the remaining characters.

Implement the function: bool isKSubsequence(string S, string T, int k)

Constraints

  • 1 <= S.length <= 10^6
  • 1 <= T.length <= 10^5
  • 1 <= k <= 10^9

Examples

Example 1:

  • Input: S = "abacaba", T = "abc", k = 2
  • Output: true
  • Explanation: T repeated 2 times is "abcabc". "abcabc" is a subsequence of "abacaba" (a...b...c...a...b...c).

Example 2:

  • Input: S = "abc", T = "abc", k = 2
  • Output: false

Edge Cases

  • k is very large: The solution must not materialize T repeated k times.
  • T contains characters not present in S.
  • T is longer than S but k is small.

Hints

Hint 1

Instead of creating the full repeated string, keep track of your current index in the source string S and your current position in the target string T.

Hint 2

Use a pointer to traverse S and perform a modulo operation on the current index of the target (T[pointer % T.length]) to simulate the repetition.

Hint 3

If you complete a full traversal of T exactly k times while still within the bounds of S, return true; otherwise, return false.

Follow-up questions

  • How would you optimize the search if S is extremely large and you need to perform this check for many different values of k?
  • What if you need to find the maximum possible value of k for which T repeated k times is a subsequence of S?
  • How does the time complexity change if you are allowed to pre-process S into an index map for each character?