Last Updated: 2 May, 2025

Growing String

Easy

Solve now

Problem statement

Bob has a string 'S' of length 'N' which he enjoys playing with. After each day, he appends the initial string 'S' to the one that he currently has. For example, if 'S' = "xyz", on the first day, the string will become "xyz", on the second day, the string becomes "xyzxyz", on the third day, the string becomes "xyzxyzxyz", and so on.

Alice has another string 'T' of length 'M'. She is curious about the earliest day when her string 'T' can be found as a subsequence in Bob's growing string.

Can you help Alice figure out the earliest day?

For Example :

Let 'N' = 3, 'S' = "xyz", M = 3, T = "xyz".
Bob's string on Day 1 is "xyz".
Is "xyz" a subsequence of "xyz"? Yes.
The earliest day is 1.
Thus, the answer is 1.

Input Format :

The first line contains two integers, 'N' and 'M'.
The second line contains the string 'S' of length 'N'.
The third line contains the string 'T' of length 'M'.

Output Format :

Return the earliest day (a positive integer starting from 1) when 'T' appears as a subsequence in Bob's string. If 'T' can never be formed as a subsequence, return -1.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

1 <= 'N', 'M' <= 10^5
'a' <= 'S', 'T' <= 'z'

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

Recognize that Bob's string on day 'D' is the initial string 'S' repeated 'D' times.
We want to find the minimum day 'D' such that 'T' is a subsequence of 'S' repeated 'D' times.
We can use dynamic programming to find the earliest point in Bob's growing string where each prefix of 'T' can be formed as a subsequence.
Let 'dp[j]' be a pair representing the earliest day and the index within that day's copy of 'S' where the prefix 'T[0...j]' can be formed as a subsequence, ending with the character 'T[j]' at that specific index in that specific copy.
Since the structure of each appended 'S' is the same, we can optimize by only storing the index within a single copy of 'S' and the day number.
To efficiently find the next occurrence of a character in 'S' from a given starting index, precompute the indices of the next occurrences of each character.

Algorithm:

Initialize 'N' = length of 'S', 'M' = length of 'T'.
Create a 2D array 'next_occ' of size 26 x (N + 1). This will store the index of the first occurrence of a character in 'S' at or after a given index. Initialize all values to -1.
- Iterate 'c' from 0 to 25 (for 'a' to 'z'):
  - Set 'next_occ[c][N]' to -1.
  - Iterate 'i' from N - 1 down to 0:
    - Set 'next_occ[c][i]' to 'next_occ[c][i + 1]'.
    - If S[i] == ('a' + c), set 'next_occ[c][i]' to 'i'.
Create a DP array 'dp' of size 'M', storing pairs of integers (day, index_in_S). Initialize all pairs with a value representing infinity (e.g., a day value greater than M, and an index value greater than or equal to N). Let's use (M + 1, N) for infinity.
Handle the base case for 'T[0]':
- Find the first occurrence of 'T[0]' in 'S' using 'next_occ[T[0] - 'a'][0]'.
- If the index 'first_idx' is not -1:
  - Set dp[0] = (1, first_idx).
- Else (T[0] is not present in S):
  - Return -1 (as T cannot be formed).
Iterate 'j' from 1 to M - 1 (to calculate dp for prefixes T[0...j]):
- Let 'prev_day' = dp[j-1].first, 'prev_idx' = dp[j-1].second.
- If 'prev_day' is infinity (M + 1), continue (T[0...j-1] cannot be formed, so T[0...j] also cannot).
- Find the next occurrence of 'T[j]' in 'S' starting from index 'prev_idx + 1' using 'next_occ[T[j] - 'a'][prev_idx + 1]'.
- Let 'curr_idx' be the result of the lookup.
- If 'curr_idx' is not -1:
  - 'T[j]' is found in the same copy of 'S' after the position where 'T[0...j-1]' ended.
  - Set dp[j] = (prev_day, curr_idx).
- Else ('curr_idx' is -1, 'T[j]' is not found in the rest of the current copy of 'S'):
  - We need to move to the next copy of 'S'. Find the first occurrence of 'T[j]' in 'S' starting from index 0 using 'next_occ[T[j] - 'a'][0]'.
  - Let 'curr_idx_from_start' be the result of the lookup.
  - If 'curr_idx_from_start' is not -1:
    - 'T[j]' is found as the first occurrence in the next copy of 'S'.
    - Set dp[j] = (prev_day + 1, curr_idx_from_start).
  - Else ('curr_idx_from_start' is -1, 'T[j]' is not present in S at all):
    - It's impossible to form 'T'. Set dp[j] to the infinity value (M + 1, N) and continue.
After the loop, the earliest day to form 'T' is stored in dp[M-1].first.
If dp[M-1].first is the infinity value (M + 1), return -1.
Else, return dp[M-1].first.

Solve now