แบบสอบถามเพื่อค้นหาอักขระที่ไม่ซ้ำตัวสุดท้ายในสตริงย่อยของสตริงที่กำหนดใน C++

ในปัญหานี้ เราได้รับสตริง str และคิวรี Q ซึ่งแต่ละอันประกอบด้วยจำนวนเต็มสองจำนวน งานของเราคือสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นเพื่อค้นหาอักขระที่ไม่ซ้ำตัวสุดท้ายในสตริงย่อยของสตริงที่กำหนดใน C++

คำอธิบายปัญหา

ในแต่ละแบบสอบถาม เรามีจำนวนเต็ม L และ R สองจำนวน เพื่อแก้ปัญหาการสืบค้น เราจะนำสตริงย่อยโดยเริ่มจากดัชนี L ถึงดัชนี R และค้นหาอักขระตัวสุดท้ายที่ไม่ซ้ำในสตริงย่อย

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล :str =“Tutorialspoint” Q =2

ข้อความค้นหา ={{4, 8}, {2, 6}}

ผลผลิต :-1 , -1

คำอธิบาย

subStr[4...8] =“เรียล” อักขระที่ไม่ซ้ำตัวสุดท้ายคือ s แต่อักขระทั้งหมดมีความถี่ 1

subStr[2...6] =“ทอเรีย” อักขระที่ไม่ซ้ำตัวสุดท้ายคือ a. แต่อักขระทั้งหมดมีความถี่ 1

แนวทางการแก้ปัญหา

เพื่อแก้ปัญหานี้ เราต้องค้นหาตัวละครที่มีความถี่ในการเกิดขึ้นเพียงครั้งเดียว สำหรับสิ่งนี้ วิธีการที่ง่ายและไม่ซับซ้อนคือการสร้างเมทริกซ์เพื่อคำนวณ charFreq[][] ในการแก้แบบสอบถาม subarray เราจะตรวจสอบความถี่ของการเกิดของอักขระทั้งหมดและส่งคืนอักขระตัวสุดท้ายด้วยความถี่ 1

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
int charFreq[256][1000] = {0};
void initialiseCharFrequency(string str, int n) {
   charFreq[(int)str[0]][0] = 1;
   for (int i = 1; i < n; i++) {
      char ch = str[i];
      for (int j = 0; j < 256; j++) {
         char charToUpdate = (char)j;
         if (charToUpdate == ch)
            charFreq[j][i] = charFreq[j][i - 1] + 1;
         else
            charFreq[j][i] = charFreq[j][i - 1];
      }
   }
}
string returnCharFromString(char x) {
   string s(1, x);
   return s;
}
string lastUniqueChar(string str, int n, int start, int end) {
   for (int i = end; i >= start; i--) {
      char ch = str[i];
   if ((charFreq[(int)ch][end] - charFreq[(int)ch][start - 1]) ==1)
      return returnCharFromString(ch);
   }
   return "-1";
}
int main() {
   string str = "TutorialsPoint";
   int len = str.length();
   int Q = 3;
   int query[Q][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
   initialiseCharFrequency(str, len);
   for (int i = 0; i < Q; i++)
      cout<<"\nFor Query "<<(i+1)<<": The last non-repeating character in the sub-string of a given string is "<<lastUniqueChar(str, len,query[i][0], query[i][1]);
}

ผลลัพธ์

For Query 1: The last non-repeating character in the sub-string of a given string is P
For Query 2: The last non-repeating character in the sub-string of a given string is o
For Query 3: The last non-repeating character in the sub-string of a given string is n