นับจำนวนสตริงที่สร้างได้จากอีกสตริงหนึ่งโดยใช้ตัวอักษรแต่ละตัวสูงสุดครั้งเดียวใน C++

เราได้รับสองสตริงคือ str1 และ str2 และงานคือคำนวณจำนวนสตริงที่สามารถสร้างขึ้นได้สมบูรณ์จากอีกสตริงหนึ่ง แต่เราสามารถใช้ตัวอักษรแต่ละตัวได้เพียงครั้งเดียวในการสร้างสตริง เช่น เราจะนำสตริง str1 และ str2 มาตรวจสอบการเกิดของ str2 ใน str1 โดยใช้ตัวอักษรของ str1 ทุกตัวครั้งเดียว

อินพุต − str_1 = "technical learning", str_2 = "learning"

เอาต์พุต − จำนวนสตริงที่สร้างได้จากอีกสตริงหนึ่งโดยใช้ตัวอักษรแต่ละตัวสูงสุดครั้งเดียว คือ 1

คำอธิบาย − ตามที่เห็น str_2 เกิดขึ้นใน str_1 พอดี 1 ครั้ง ดังนั้นจำนวน str_1 ใน str_2 คือ 1

อินพุต − str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

เอาต์พุต − จำนวนสตริงที่สร้างได้จากอีกสตริงหนึ่งโดยใช้ตัวอักษรแต่ละตัวสูงสุดครั้งเดียว คือ 3

คำอธิบาย − str_2 คือ hello เราจะตรวจสอบการสร้างคำ hello โดยใช้ตัวอักษรของ str_1 ครั้งเดียว ตามที่เห็น มีการสร้างคำ hello ได้ 3 ครั้งใน str_1 ดังนั้นจำนวนคือ 3

แนวทางที่ใช้ในโปรแกรม

• รับสตริง str_1 และ str_2 คำนวณความยาว ส่งไปฟังก์ชันประมวลผล
• ประกาศตัวแปรชั่วคราว count เก็บจำนวน str_2 ใน str_1 เริ่มต้นด้วย INT_MAX (INT_MAX ใน C++ ระบุค่าสูงสุดที่ตัวแปรเก็บได้ คือ +2147483647)
• สร้างอาเรย์ขนาด 26 (ตัวอักษรภาษาอังกฤษ 26 ตัว) เริ่มต้นเป็น 0
• ลูป FOR จาก 0 ถึงความยาว str_1 เพิ่ม arr[str_1[i] - 'a'] ขึ้น 1
• ลูป FOR อีกชั้นจาก 0 ถึงความยาว str_2 กำหนด count = min(count, arr[str_2[i] - 'a'])
• คืนค่า count
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int atmost_once(string str_1, int len_str1, string str_2, int len_str2){
    int count = INT_MAX;
    int arr[26] = { 0 };
    for (int i = 0; i < len_str1 ; i++){
        arr[str_1[i] - 'a'] += 1;
    }
    for (int i = 0; i < len_str2; i++){
        count = min(count, arr[str_2[i] - 'a']);
    }
    return count;
}

int main(){
    string str_1 = "technical learning";
    int length_str1 = str_1.length();
    string str_2 = "learning";
    int length_str2 = str_2.length();
    cout<<"Count of strings that can be formed from another string using each character at-most once are: "<<atmost_once(str_1,length_str1, str_2, length_str2);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of strings that can be formed from another string using each character at-most once are: 1