|
Given a 0-indexed string s, and a 2D array of integers queries, where queries[i] = [li, ri] represents a substring of s starting from the index li and ending at the index ri (both inclusive), i.e. s[li..ri]. A 0-indexed string t of length n is called same-end if it has the same character at both of its ends, i.e., t[0] == t[n – 1]. The task is to return an array ans where ans[i] is the number of same-end substrings of queries[i].
Example:
Input: s = “abcaab”, queries = {{0,0},{1,4},{2,5},{0,5}}
Output: {1,5,5,10}
Explanation: Here is the same-end substrings of each query:
- 1st query: s[0..0] is “a” which has 1 same-end substring: “a“.
- 2nd query: s[1..4] is “bcaa” which has 5 same-end substrings: “bcaa”, “bcaa”, “bcaa”, “bcaa“, “bcaa“.
- 3rd query: s[2..5] is “caab” which has 5 same-end substrings: “caab”, “caab”, “caab”, “caab“, “caab”.
- 4th query: s[0..5] is “abcaab” which has 10 same-end substrings: “abcaab”, “abcaab”, “abcaab”, “abcaab”, “abcaab”, “abcaab“, “abcaab”, “abcaab”, “abcaab”, “abcaab“.
Input: s = “abcd”, queries = {{0,3}}
Output: {4}
Explanation: The only query is s[0..3] which is “abcd”. It has 4 same-end substrings: “abcd”, “abcd”, “abcd”, “abcd”.
Approach:
Store for each character c from a … z for upto each index i. Then we count for each query from L to R the frequency of each character in the range and we count the number of possible substrings with that character c.
Consider this :
String s = abaabcbcbca
For a Query [ 1 , 4 ] here we have a[baabcb]cbca we have
For b we can pair each the number of characters in front of it
So if b is present 3 times we can create 3 + 2 + 1 = 6 substrings with b as start and end.
Generalizing we can get if for a query we have k times the character c then K + K-1 + K-2 + K-3 + … + 1 substrings are possible so the answer is K*(K+1)/2
Steps-by-step approach:
- Create result vector ans, get number of queries Q, and length of string N.
- Create and populate frequency vector freq to store character frequencies.
- Process each query: calculate count of substrings with same end character.
- Calculate total substrings for each character within query indices.
- Store counts of substrings for each query in ans.
- Return ans containing counts of substrings for each query.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of substrings with the same
// end character
vector<int>
sameEndSubstringCount(string s,
vector<vector<int> >& queries)
{
// Initialize the result vector
vector<int> ans;
// Get the number of queries and the length of the
// string
int Q = queries.size();
int N = s.size();
// Create a 2D vector to store the frequency of each
// character in the string
vector<vector<int> > freq(N + 1, vector<int>(26, 0));
// Populate the frequency vector
for (int i = 1; i <= N; i++) {
// Copy the frequency of the previous index
freq[i] = freq[i - 1];
// Increment the frequency of the current character
freq[i][s[i - 1] - 'a'] += 1;
}
// Iterate over each query
for (int i = 0; i < Q; i++) {
// Get the left and right indices of the query
int L = queries[i][0] + 1, R = queries[i][1] + 1;
// Initialize the total number of substrings
int total_substrings = 0;
// Iterate over each character
for (int c = 0; c < 26; c++) {
// Get the count of the character in the
// substring
int cnt = freq[R][c] - freq[L - 1][c];
// Add the number of substrings that can be
// formed with this character
total_substrings += (cnt * (cnt + 1)) / 2;
}
// Add the total number of substrings to the result
// vector
ans.push_back(total_substrings);
}
// Return the result vector
return ans;
}
// Driver code
int main()
{
// Create a string
string s = "abcaab";
// Create a vector of queries
vector<vector<int> > queries
= { { 0, 0 }, { 1, 4 }, { 2, 5 }, { 0, 5 } };
// Get the result vector
vector<int> result = sameEndSubstringCount(s, queries);
// Print the result vector
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
import java.util.*;
public class SameEndSubstringCount {
// Function to count the number of substrings with the
// same end character
static List<Integer>
sameEndSubstringCount(String s,
List<List<Integer> > queries)
{
// Initialize the result list
List<Integer> ans = new ArrayList<>();
// Get the number of queries and the length of the
// string
int Q = queries.size();
int N = s.length();
// Create a 2D array to store the frequency of each
// character in the string
int[][] freq = new int[N + 1][26];
// Populate the frequency array
for (int i = 1; i <= N; i++) {
// Copy the frequency of the previous index
System.arraycopy(freq[i - 1], 0, freq[i], 0,
26);
// Increment the frequency of the current
// character
freq[i][s.charAt(i - 1) - 'a'] += 1;
}
// Iterate over each query
for (List<Integer> query : queries) {
// Get the left and right indices of the query
int L = query.get(0) + 1, R = query.get(1) + 1;
// Initialize the total number of substrings
int totalSubstrings = 0;
// Iterate over each character
for (int c = 0; c < 26; c++) {
// Get the count of the character in the
// substring
int cnt = freq[R][c] - freq[L - 1][c];
// Add the number of substrings that can be
// formed with this character
totalSubstrings += (cnt * (cnt + 1)) / 2;
}
// Add the total number of substrings to the
// result list
ans.add(totalSubstrings);
}
// Return the result list
return ans;
}
// Driver code
public static void main(String[] args)
{
// Create a string
String s = "abcaab";
// Create a list of queries
List<List<Integer> > queries = new ArrayList<>();
queries.add(Arrays.asList(0, 0));
queries.add(Arrays.asList(1, 4));
queries.add(Arrays.asList(2, 5));
queries.add(Arrays.asList(0, 5));
// Get the result list
List<Integer> result
= sameEndSubstringCount(s, queries);
// Print the result list
for (int i : result) {
System.out.print(i + " ");
}
System.out.println();
}
}
// This code is contributed by shivamgupta0987654321
def same_end_substring_count(s, queries):
# Initialize the result list
ans = []
# Get the length of the string
N = len(s)
# Create a 2D array to store the frequency of each character in the string
freq = [[0] * 26 for _ in range(N + 1)]
# Populate the frequency array
for i in range(1, N + 1):
# Copy the frequency of the previous index
freq[i] = freq[i - 1][:]
# Increment the frequency of the current character
freq[i][ord(s[i - 1]) - ord('a')] += 1
# Iterate over each query
for query in queries:
# Get the left and right indices of the query
L, R = query[0] + 1, query[1] + 1
# Initialize the total number of substrings
total_substrings = 0
# Iterate over each character
for c in range(26):
# Get the count of the character in the substring
cnt = freq[R][c] - freq[L - 1][c]
# Add the number of substrings that can be formed with this character
total_substrings += (cnt * (cnt + 1)) // 2
# Add the total number of substrings to the result list
ans.append(total_substrings)
# Return the result list
return ans
# Driver code
if __name__ == "__main__":
# Create a string
s = "abcaab"
# Create a list of queries
queries = [
[0, 0],
[1, 4],
[2, 5],
[0, 5]
]
# Get the result list
result = same_end_substring_count(s, queries)
# Print the result list
print(" ".join(map(str, result)))
function sameEndSubstringCount(s, queries) {
// Initialize the result array
const ans = [];
// Get the length of the string
const N = s.length;
// Create a 2D array to store the frequency of each character in the string
const freq = Array.from({ length: N + 1 }, () => Array(26).fill(0));
// Populate the frequency array
for (let i = 1; i <= N; i++) {
freq[i] = [...freq[i - 1]];
freq[i][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)]++;
}
// Iterate over each query
for (let i = 0; i < queries.length; i++) {
// Get the left and right indices of the query
const [L, R] = queries[i];
// Initialize the total number of substrings
let totalSubstrings = 0;
// Iterate over each character
for (let c = 0; c < 26; c++) {
// Get the count of the character in the substring
const cnt = freq[R + 1][c] - freq[L][c];
// Add the number of substrings that can be formed with this character
totalSubstrings += (cnt * (cnt + 1)) / 2;
}
// Add the total number of substrings to the result array
ans.push(totalSubstrings);
}
// Return the result array
return ans;
}
// Driver code
function main() {
// Create a string
const s = "abcaab";
// Create a 2D array of queries
const queries = [[0, 0], [1, 4], [2, 5], [0, 5]];
// Get the result array
const result = sameEndSubstringCount(s, queries);
// Print the result array
console.log(result.join(" "));
}
// Invoke the main function
main();
Time complexity: O(max(N,Q)ā26)
Auxiliary space: O(Nā26)
|
