Coding Week 11 - Strings Flashcards
Problem 1) Count Unique Characters of All Substring Of a Given String
Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.
For example, calling countUniqueChars(s) if s = “LEETCODE” then “L”, “T”, “C”, “O”, “D” are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = “ABC”
Output: 10
Explanation: All possible substrings are: “A”,”B”,”C”,”AB”,”BC” and “ABC”.
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: s = “ABA”
Output: 8
Explanation: The same as example 1, except countUniqueChars(“ABA”) = 1.
Example 3:
Input: s = “LEETCODE”
Output: 92
Question 1) The count of unique characters of all substring of the ‘S’ is equal to:
A) Sum of total contribution of each character present in ‘S’ (as unique characters) in all substrings of ‘S’.
B) Sum of total contribution of each character present in ‘S’ in all substrings of ‘S’.
C) Sum of total contribution of each character from (A - Z) in all substrings of ‘S’.
D) Multiplication of total contribution of each character present in ‘S’ (as unique characters) in all substrings of ‘S’.
A) Sum of total contribution of each character present in ‘S’ (as unique characters) in all substrings of ‘S’.
A character will only contribute to the substring if all other characters in the substring are different from it. So, if we find the total contribution of each character present in ‘S’ where it is uniquely present, we can just add them to get the final answer.
Problem 1) Count Unique Characters of All Substring Of a Given String
Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.
For example, calling countUniqueChars(s) if s = “LEETCODE” then “L”, “T”, “C”, “O”, “D” are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.
Notice that some substrings can be repeated so in this case you have to count the repeated ones too.
Example 1:
Input: s = “ABC”
Output: 10
Explanation: All possible substrings are: “A”,”B”,”C”,”AB”,”BC” and “ABC”.
Every substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10
Example 2:
Input: s = “ABA”
Output: 8
Explanation: The same as example 1, except countUniqueChars(“ABA”) = 1.
Example 3:
Input: s = “LEETCODE”
Output: 92
Question 1) What is the minimum time and auxiliary space possible to solve this problem?
A) Time - O(N ^ 2), Space - O(N)
B) Time - O(1), Space - O(1)
C) Time - O(N), Space - O(N)
D) Time - O(N), Space - O(1)
D) Time - O(N), Space - O(1)
To find the total contribution of each character we will use the following concept:
If a character c = s[i] is unique, its total contribution is (i+1)*(N-i)
If a character c = s[i] is not unique, it will contribute within a restricted window. For example if
s = “c ….. c …. c.”
the middle c will contribute only within the window c [….. c ….] c
Now the problem becomes easy. At every position, just ask yourself,
When did I last see this character?
When will I next see this character?
If a character c = s[i] is non-unique, its total contribution is (i - prevSeen[i] ) * ( nextSeen[i] - i )
Now, we can find prevSeen[] and and nextSeen[] for each S[i] in O(N).
Then we can sum of (i - prevSeen[i] ) * ( nextSeen[i] - i ) for each i in O(N).
Hence, the time complexity will be O(N).
For each character, we have to store the previous index and next index. And there are only 26 characters. While traversing each character we can find its contribution and update the previous index. Hence, the space complexity will be constant.
Problem 2) Number Of Ways To Select Buildings
You are given a 0-indexed binary string s which represents the types of buildings along a street where:
s[i] = ‘0’ denotes that the ith building is an office and
s[i] = ‘1’ denotes that the ith building is a restaurant.
As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.
For example, given s = “001101”, we cannot select the 1st, 3rd, and 5th buildings as that would form “011” which is not allowed due to having two consecutive buildings of the same type.
Return the number of valid ways to select 3 buildings.
Example 1:
Input: s = “001101”
Output: 6
Explanation:
The following sets of indices selected are valid:
- [0,2,4] from “001101” forms “010”
- [0,3,4] from “001101” forms “010”
- [1,2,4] from “001101” forms “010”
- [1,3,4] from “001101” forms “010”
- [2,4,5] from “001101” forms “101”
- [3,4,5] from “001101” forms “101”
No other selection is valid. Thus, there are 6 total ways.
Question 1) What will be the contribution of ‘1’ which has ‘X’ zeros to its left and ‘Y’ zeroes to its right?
A) X + Y
B) X - Y
C) X * Y
D) X * Y - 1
C) X * Y
For each zero on the left of ‘1’, we have Y choices on the right side of ‘1’
Example: “000100”, the answer will be 6.
0 _ _ 1 0 _
_ 0 _ 1 0 _
_ _ 0 1 0 _
0 _ _ 1 _ 0
_ 0 _ 1 _ 0
_ _ 0 1 _ 0
