count-valid-substrings-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 a string <code>s</code> consisting only of the characters <code>&#39;a&#39;</code>, <code>&#39;b&#39;</code>, and <code>&#39;c&#39;</code>.

A string is called valid if it does not contain <code>&quot;abc&quot;</code> as a substring.

Return the number of valid substrings in <code>s</code>. Substrings with different starting or ending indices are counted separately.

A substring is a contiguous non-empty sequence of characters within a string.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;abac&quot;

Output: 10

Explanation:

The following substrings don&#39;t contain <code>&quot;abc&quot;</code>​​​​​​​ as a substring:

<ul>
	<li><code>s[0..0] = &quot;a&quot;</code></li>
	<li><code>s[0..1] = &quot;ab&quot;</code></li>
	<li><code>s[0..2] = &quot;aba&quot;</code></li>
	<li><code>s[0..3] = &quot;abac&quot;</code>​​​​​​​</li>
	<li><code>s[1..1] = &quot;b&quot;</code></li>
	<li><code>s[1..2] = &quot;ba&quot;</code></li>
	<li><code>s[1..3] = &quot;bac&quot;</code></li>
	<li><code>s[2..2] = &quot;a&quot;</code></li>
	<li><code>s[2..3] = &quot;ac&quot;</code></li>
	<li><code>s[3..3] = &quot;c&quot;</code></li>
</ul>

Thus, the answer is 10.
</div>

Example 2:

<div class="example-block">
Input: s = &quot;abc&quot;

Output: 5

Explanation:

The following substrings don&#39;t contain <code>&quot;abc&quot;</code>​​​​​​​ as a substring:

<ul>
	<li><code>s[0..0] = &quot;a&quot;</code></li>
	<li><code>s[0..1] = &quot;ab&quot;</code></li>
	<li><code>s[1..1] = &quot;b&quot;</code></li>
	<li><code>s[1..2] = &quot;bc&quot;</code></li>
	<li><code>s[2..2] = &quot;c&quot;</code>​​​​​​​</li>
</ul>

Thus, the answer is 5.
</div>

Example 3:

<div class="example-block">
Input: s = &quot;ac&quot;

Output: 3

Explanation:

All substrings in <code>s</code> don&#39;t contain <code>&quot;abc&quot;</code> as a substring​​​​​​​. Thus, the answer is 3.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code>​​​​​​​</li>
	<li><code>s</code> only consists of <code>&#39;a&#39;</code>, <code>&#39;b&#39;</code>, and <code>&#39;c&#39;</code> characters.</li>
</ul>

Biweekly Contest 195

biweekly-contest-195

countValidSubstrings

Senior

Count Valid Substrings I

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

You are given a string s consisting only of the characters 'a', 'b', and 'c'.

A string is called valid if it does not contain "abc" as a substring.

Return the number of valid substrings in s. Substrings with different starting or ending indices are counted separately.

A substring is a contiguous non-empty sequence of characters within a string.

 

Example 1:

Input: s = "abac"

Output: 10

Explanation:

The following substrings don't contain "abc" as a substring:

 * s[0..0] = "a"
 * s[0..1] = "ab"
 * s[0..2] = "aba"
 * s[0..3] = "abac"
 * s[1..1] = "b"
 * s[1..2] = "ba"
 * s[1..3] = "bac"
 * s[2..2] = "a"
 * s[2..3] = "ac"
 * s[3..3] = "c"

Thus, the answer is 10.

Example 2:

Input: s = "abc"

Output: 5

Explanation:

The following substrings don't contain "abc" as a substring:

 * s[0..0] = "a"
 * s[0..1] = "ab"
 * s[1..1] = "b"
 * s[1..2] = "bc"
 * s[2..2] = "c"

Thus, the answer is 5.

Example 3:

Input: s = "ac"

Output: 3

Explanation:

All substrings in s don't contain "abc" as a substring . Thus, the answer is 3.

 

Constraints:

 * 1 <= s.length <= 105
 * s only consists of 'a', 'b', and 'c' characters.