FastPrepFastPrep
Problem Brief

Count Similar Substrings (Microsoft India) 🐱

FULLTIMEOA
See Microsoft online assessment and hiring insights

A string s, is similar to another string t, if it possible to swap two adjacent characters at most once in s to turn it into t. Given a keyword string named key, find how many substrings of text are similar to key.

1Example 1

Input
key = "moon", text = "monomon"
Output
2
Explanation
Consider the first four characters in text. i.e "mono". Swap the last two characters to match the keyword "moon". The last four characters in the text are "omon". Swap the first two characters to match the keyword. Thus, there are 2 substrings of "monomon" that are similar to "moon". Note, that no other substring is similar to the given key.

2Example 2

Input
key = "aaa", text = "aaaa"
Output
2
Explanation
There are 2 substrings of "aaaa" that are similar to "aaa" are:
  • aaaa
  • aaaa

    • 3Example 3

    Input
    key = "xxy", text = "zxxyxyx"
    Output
    3
    Explanation
    No explanation is provided for now 👩‍🌾

    Constraints

    Limits and guarantees your solution can rely on.

  • key and text will consist solely of lowercase English letters.
  • 1 <= |key| <= |text| <= 50, where |s| denotes the length of a string s.
    • public int countSimilarSubstrings(String key, String text) {
  // write your code here
}
    Input

    key

    "moon"

    text

    "monomon"

    Output

    2

    Sign in to submit your solution.