Skip to main content

Oracle

Oracle OA 2024 - Substring Search


Given a string, determine how many different substrings exist in it that have no repeating characters. Two substrings are considered different if they have a different start or end index.

Example:
For the string "abac":

The substrings that have no repeating characters are:

  • "a", "b", "a", "c", "ab", "ac", and "bac".

Note that "aba" and "abac" do not qualify because the character 'a' is repeated in them. Also, two substrings, "a" and "a", both qualify because their start indices are different: s[0] and s[2].

Thus, there are 8 substrings that have no repeating characters.

Function Description:

Complete the function findSubstrings in the editor below.

findSubstrings has the following parameter:

  • string s: the given string.

Returns:

  • The number of substrings in s that have no repeating characters.

Constraints:

  • (1 <= length of s <= 10^5)
  • (s) consists of only lowercase English letters (ASCII: ['a' - 'z']).

Sample Input for Custom Testing:

bcada

Output:

9

Explanation:
For the string "bcada", the substrings with no repeating characters are:

  • "b", "c", "a", "d", "bc", "ca", "ad", "bca", and "cad".

Thus, there are 9 substrings that meet the criteria.

Given a string, determine how many different substrings exist in it that have no repeating characters. Two substrings are considered different if they have a different start or end index.

Example:
For the string "abac":

The substrings that have no repeating characters are:

  • "a", "b", "a", "c", "ab", "ac", and "bac".

Note that "aba" and "abac" do not qualify because the character 'a' is repeated in them. Also, two substrings, "a" and "a", both qualify because their start indices are different: s[0] and s[2].

Thus, there are 8 substrings that have no repeating characters.

Function Description:

Complete the function findSubstrings in the editor below.

findSubstrings has the following parameter:

  • string s: the given string.

Returns:

  • The number of substrings in s that have no repeating characters.

Constraints:

  • (1 <= length of s <= 10^5)
  • (s) consists of only lowercase English letters (ASCII: ['a' - 'z']).

Sample Input for Custom Testing:

bcada

Output:

9

Explanation:
For the string "bcada", the substrings with no repeating characters are:

  • "b", "c", "a", "d", "bc", "ca", "ad", "bca", and "cad".

Thus, there are 9 substrings that meet the criteria.