Truy vấn để tìm ký tự không lặp lại cuối cùng trong chuỗi con của một chuỗi đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp các truy vấn chuỗi str và Q, mỗi truy vấn bao gồm hai số nguyên. Nhiệm vụ của chúng ta là tạo chương trình giải các Truy vấn để tìm ký tự không lặp lại cuối cùng trong chuỗi con của một chuỗi đã cho trong C ++.

Mô tả vấn đề

Trong mỗi truy vấn, chúng ta có hai số nguyên L và R. Để giải quyết các truy vấn, chúng ta sẽ lấy một chuỗi con bắt đầu từ chỉ mục L đến chỉ mục R. Và tìm ký tự cuối cùng không lặp lại trong chuỗi con.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :str =“Tutorialspoint” Q =2

truy vấn ={{4, 8}, {2, 6}}

Đầu ra :-1, -1

Giải thích

subStr [4 ... 8] =“rials”. Ký tự không lặp lại cuối cùng là s. Nhưng tất cả các ký tự đều có tần số 1.

subStr [2 ... 6] =“toria”. Ký tự không lặp lại cuối cùng là a. Nhưng tất cả các ký tự đều có tần số 1.

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần tìm ký tự có tần suất xuất hiện duy nhất. Đối với điều này, một cách tiếp cận dễ dàng và đơn giản là tạo một ma trận để tính toán charFreq [] []. Để giải quyết truy vấn mảng con, chúng tôi sẽ kiểm tra tần suất xuất hiện của tất cả các ký tự và trả về ký tự cuối cùng có tần suất 1.

Ví dụ

#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]);
}

Đầu ra

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