首页 > 其他分享 >LeetCode 1915. Number of Wonderful Substrings

LeetCode 1915. Number of Wonderful Substrings

时间:2024-05-14 08:56:56浏览次数:19  
标签:count aba word aabb substrings Substrings Wonderful wonderful 1915

原题链接在这里:https://leetcode.com/problems/number-of-wonderful-substrings/description/

题目:

A wonderful string is a string where at most one letter appears an odd number of times.

  • For example, "ccjjc" and "abab" are wonderful, but "ab" is not.

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

Constraints:

  • 1 <= word.length <= 105
  • word consists of lowercase English letters from 'a' to 'j'.

题解:

To count the number of fulfilling substrings, we need to maintain the prefix count.

Since the word only consist 'a' to 'j' that is 10 letters, then we can use a state of then diigts to note the previous state. each digit dentoes how many previous letter occurs % 2.

Then there could be 1 << 10 different states. 

Use count to maintain all the state counts.

count[0] = 1 for no letter, the count is 1. Then later "aa" occurs, its state is "000000000", accumulate the count[0] to result.

Since it is at most one letter, there are two types.

One is all the even freq. res += count[state]. state are the same for this substring

The other is flip one letter. from a to j, try flip its corresponding index.

Time Complexity: O(n). n = word.length().

Space: O(1). 

AC Java:

 1 class Solution {
 2     public long wonderfulSubstrings(String word) {
 3         long[] count = new long[1 << 10];
 4         count[0] = 1;
 5         int state = 0;
 6         long res = 0;
 7         int n = word.length();
 8         for(int i = 0; i < n; i++){
 9             int val = word.charAt(i) - 'a';
10             state ^= (1 << val); // state[i]
11             res += count[state]; // all letter freq are even
12             for(int k = 0; k < 10; k++){
13                 int stateOdd = state ^ (1 << k); // flip one letter
14                 res += count[stateOdd];
15             }
16 
17             count[state]++;
18         }
19 
20         return res;
21     }
22 }

 

标签:count,aba,word,aabb,substrings,Substrings,Wonderful,wonderful,1915
From: https://www.cnblogs.com/Dylan-Java-NYC/p/18190515

相关文章

  • ABC240Ex Sequence of Substrings
    ABC240ExSequenceofSubstringsLIS的好题改编。约定\(S(l,r)\)为字符串\(s\)中第\(l\)位到底\(r\)​位。\(S(l,r)<S(x,y)\)为字符串中\([l,r]\)的子串字典序比\([x,y]\)的子串小。前置LIS的\(n\logn\)求法。题解我们考虑按照类似于朴素LIS的方式设状......
  • [题解]CF33C Wonderful Randomized Sum
    CF33CWonderfulRandomizedSum我们可以发现,如果两区间不交叉也不会影响到结果,所以我们只需要考虑不交叉的情况即可。我们所选择的前缀\(1\simi\)应满足区间和最小,后缀也一样。所以用两个数组\(lr,rl\)分别记录下\(1\simi\)(前缀)最小和、\(i\simn\)(后缀)最小和。然后枚举分割......
  • CF1915B Not Quite Latin Square 题解
    CF1915B题意给出一个\(3\)行\(3\)列的字符矩形,其中每行都有字符ABC各一个组成,现有一个字符未知,求出未知字符。思路就是说每个字符都应该出现\(3\)次,所以我们只要找到出现两次的字符即可。ACCode#include<bits/stdc++.h>usingnamespacestd;intt;chara[10][10......
  • CF1930D1 - Sum over all Substrings (Easy Version)
    对于每一个\(f(i,j)\),我们考虑如何计算。我们发现,\(\texttt{1010}\)式的字符串很有用,所以这启发我们如果遇到了一个模式\(p_i=\texttt{'1'}\),那么我们可以在\(i+1\)的位置放一个\(\texttt{'1'}\)。这样我们直接处理了\(i,i+1,i+2\)。容易证明这是最优的。#incl......
  • UVA10829 L-Gap Substrings
    我永远喜欢数据结构。貌似是此题中第一个使用SA+分治+二维数点做法的题解?题目传送门给出字符串\(s\)和常数\(g\),求出有多少四元组\((l_1,r_1,l_2,r_2)\),满足\(s[l_1,r_1]=s[l_2,r_2]\)且\(r_1+g+1=l_2\)。\(T\)组数据,\(1\leT,g\le10\),\(|s|\le5\times10......
  • Gym-101915D 题解
    D给定一张图,分为左右各\(P\)个点,左右各自内部是一个完全图,左右之间有\(m\)条边。求这个图的最大团。\(P\le20,m\leP^2\)。对于每个右部点,求出一个长度为\(20\)的二进制数,第\(i\)位是\(1\)表示它与左部第\(i\)点有连边。枚举右部点的子集\(S\),将它们的二进制数......
  • CF1915G Bicycles 题解
    分析参照去年普及组T4,很显然能发现就是一个暴力最短路。设\(dis_{i,j}\)表示从\(1\)走到\(i\)且能得到的\(s\)最小为\(j\)时的最短路。那么答案就是\(\min\{dis_{n,i}|1\lei\leV\}\)。考虑最短路转移。对于当前的\(dis_{u,j}\),走到\(v\)的代价将会是\(w_{u......
  • CF1915D Unnatural Language Processing 题解
    容易发现音节的划分不仅要求子串形如\(\texttt{CV}\)或\(\texttt{CVC}\),并且接下来的两个字符也必须是\(\texttt{CV}\),不然会导致无法划分下去。于是我们遍历字符串,找出所有满足上述条件的子串,记录需要输出\(\texttt{.}\)的位置即可。实现:intn;strings,ans,t="";cin>......
  • CF1915E Romantic Glasses 题解
    我们考虑维护\(sum_i\)表示前\(i\)个数中偶数下标的数之和与奇数下标的数之和之差,其中\(sum_0=0\)。若在某一时刻,有\(sum_i=sum_j(j<i)\),说明\(j\simi\)中偶数下标的数之和与奇数下标的数之和之差为\(0\)。这个使用map判断即可。实现:intn,f=0;cin>>n;m.clear()......
  • 2..3...4.... Wonderful! Wonderful! 题解
    2..3...4....Wonderful!Wonderful!题目描述​ 有一个元素等于其下标的数组,长度为n,对于属于区间\([1,(n-1)/2]\)的每一个数,我们称其为k,我们可以对数组进行任意次数的操作。​ 操作:选择长度为\(2*k+1\)的子序列,然后只留下最中间的那个数,删掉其他的元素。​ 我们想知道对于每个......