count-substrings-that-can-be-rearranged-to-contain-a-string-i

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given two strings <code>word1</code> and <code>word2</code>.

A string <code>x</code> is called valid if <code>x</code> can be rearranged to have <code>word2</code> as a prefix.

Return the total number of valid substrings of <code>word1</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: word1 = &quot;bcca&quot;, word2 = &quot;abc&quot;

Output: 1

Explanation:

The only valid substring is <code>&quot;bcca&quot;</code> which can be rearranged to <code>&quot;abcc&quot;</code> having <code>&quot;abc&quot;</code> as a prefix.
</div>

Example 2:

<div class="example-block">
Input: word1 = &quot;abcabc&quot;, word2 = &quot;abc&quot;

Output: 10

Explanation:

All the substrings except substrings of size 1 and size 2 are valid.
</div>

Example 3:

<div class="example-block">
Input: word1 = &quot;abcabc&quot;, word2 = &quot;aaabc&quot;

Output: 0
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word1.length &lt;= 105</code></li>
	<li><code>1 &lt;= word2.length &lt;= 104</code></li>
	<li><code>word1</code> and <code>word2</code> consist only of lowercase English letters.</li>
</ul>