เราได้รับสตริง str[] ที่มี 'a', 'b' และ 'c' เท่านั้น เป้าหมายคือการค้นหาสตริงย่อยของ str[] เพื่อให้อักขระทั้งสามไม่ได้เป็นส่วนหนึ่งของสตริงย่อยนั้น สำหรับสตริง str สตริงย่อยอาจเป็น "a", "b", "c", "abb", "bba", "bc", "ca", "ccc" แต่ไม่ใช่ "abc", "bcca" , " cab” เพราะมี 'a', 'b' และ 'c' ทั้งสามตัว
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − str[] =“aabc”
ผลผลิต − จำนวนสตริงย่อยที่ไม่มีอักขระทั้งหมดจากชุด {'a', 'b', 'c'} พร้อมกันคือ − 8
คำอธิบาย − สตริงย่อยจะเป็น :“a”, “a”, “b”, “c”, “aa”, “ab”, “bc”, “aab”
ป้อนข้อมูล − str[] =“abcabc”
ผลผลิต − จำนวนสตริงย่อยที่ไม่มีอักขระทั้งหมดจากชุด {'a', 'b', 'c'} พร้อมกันคือ − 11
คำอธิบาย − สตริงย่อยจะเป็น :“a”, “b”, “c”, “a”, “b”, “c”, “ab”, “bc”, “ca”, “ab”, “bc”
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางนี้ เราทราบดีว่าจำนวนสตริงย่อยทั้งหมดของสตริงที่มีอักขระ n ตัวคือ n*(n+1)/2.
ตอนนี้เราจะสำรวจสตริงและสำหรับอักขระแต่ละประเภท 'a', 'b' หรือ 'c' เราจะตรวจสอบดัชนีก่อนหน้าของอักขระอีกสองตัวที่เหลือ ('b','c'), ('c','a') และ ('a', 'b') เพียงลบดัชนีขั้นต่ำของอีกสองตัวออกจากการนับ เนื่องจากเรารู้ว่าเรากำลังลบอักขระนั้นเพื่อรวมอักขระปัจจุบันในสตริงย่อยเพื่อไม่ให้มีทั้งสามตัว
-
ใช้สตริงสตริงเป็นอาร์เรย์อักขระ
-
ฟังก์ชัน sub_without_all(char str[], int size) รับสตริง ซึ่งมีความยาวและส่งกลับจำนวนสตริงย่อยที่ไม่มี 'a', 'b' และ 'c' รวมกันทั้งหมด
-
ใช้ขนาดการนับเริ่มต้น*(size+)/2 สำหรับจำนวนสตริงย่อยที่เป็นไปได้ทั้งหมดของ str[]
-
นำตัวแปร a,b,c เพื่อเก็บดัชนีสุดท้ายของ 'a', 'b', 'c' ใน str[] เริ่มต้นทั้งหมดด้วย 0
-
Traverse str[] ใช้ for loop จาก i=0 ถึง i
-
ถ้า str[i]=='a' อัปเดตดัชนีของ 'a' เป็น a=i+1 ลบดัชนีขั้นต่ำของ 'b' หรือ 'c' จากการนับเพื่อรวม 'a' ในสตริงย่อย ลบ b,c แล้วแต่จำนวนใดจะน้อยที่สุดจากการนับ
-
ทำแบบเดียวกับขั้นตอนก่อนหน้าสำหรับ str[i]==’b’ หรือ str[i]==’c’
-
ในตอนท้ายเราจะนับเป็นสตริงย่อยของ str[] โดยไม่มีอักขระทั้งสามตัวในครั้งเดียว
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = c = 0;
for (int i = 0; i < size; i++){
if (str[i] == 'a'){
a = i + 1;
count -= min(b, c);
}
else if (str[i] == 'b'){
b = i + 1;
count -= min(a, c);
}
else{
c = i + 1;
count -= min(a, b);
}
}
return count;
}
int main(){
char str[] = "abcabbc";
int size = strlen(str);
cout<<"Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at
the same time are: "<<sub_without_all(str, size);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15 