FastPrep
Problem · String

Count Similar Substrings (Microsoft India) 🐱

Learn this problem
● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

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.

Function

countSimilarSubstrings(key: String, text: String) → int

Examples

Example 1

key = "moon"text = "monomon"return = 2
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.

Example 2

key = "aaa"text = "aaaa"return = 2
There are 2 substrings of "aaaa" that are similar to "aaa" are:
  • aaaa
  • aaaa

    • Example 3

    key = "xxy"text = "zxxyxyx"return = 3
    No explanation is provided for now 👩‍🌾

    Constraints

  • key and text will consist solely of lowercase English letters.
  • 1 <= |key| <= |text| <= 50, where |s| denotes the length of a string s.

    • More Microsoft problems

    drafts saved locally
    public int countSimilarSubstrings(String key, String text) {
  // write your code here
}
    key"moon"
    text"monomon"
    expected2
    checking account