FastPrep
Problem · Dynamic Programming

String Transformation (Also for Infra Automation Intern)

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

The NLP enthusiasts of Hackerland are working on a string transformation algorithm. In a single operation, a string s can be transformed into another string by removing a suffix of the string and adding the removed suffix in front of the remaining string. For example, the string "abcd" can be transformed to "dabc" by removing the suffix "d" and adding it to the front of the remaining string "abc".

Given two strings src and target of lowercase English characters and an integer k, find the number of ways to transform the string src to the string target using the given algorithm in exactly k steps. Since the answer can be large, report it modulo 10^9 + 7.

Note: Two ways are considered different if the sequence of indices chosen for breaking the suffix is different at 1 or more steps.

Function

getNumWays(src: String, target: String, k: int) → int

Complete the function getNumWays in the editor.

getNumWays has the following parameter(s):

  1. 1. string src: the source string
  2. 2. string target: the target string
  3. 3. int k: the number of steps

Returns

int: the number of ways modulo 10^9 + 7

Examples

Example 1

src = "ababab"target = "ababab"k = 1return = 2
Choose the suffixes "abab" and "ab" to transform src to target in a single operation.

Example 2

src = "aaaa"target = "aaaa"k = 2return = 9
All sequences of operations convert src to the target.

Example 3

src = "aaaa"target = "aaaa"k = 2return = 9
All sequences of operations convert src to the target.

Constraints

  • 2 ≤ length(src) ≤ 1000
  • 2 ≤ length(target) ≤ 1000
  • 1 ≤ k ≤ 10^6

More Snowflake problems

drafts saved locally
public int getNumWays(String src, String target, int k) {
  // write your code here
}
src"ababab"
target"ababab"
k1
expected2
checking account