C++에서 주어진 문자열의 하위 문자열에서 반복되지 않는 마지막 문자를 찾는 쿼리

이 문제에서는 각각 두 개의 정수로 구성된 문자열 str과 Q 쿼리가 제공됩니다. 우리의 임무는 C++에서 주어진 문자열의 하위 문자열에서 반복되지 않는 마지막 문자를 찾기 위해 쿼리를 해결하는 프로그램을 만드는 것입니다.

문제 설명

각 쿼리에는 두 개의 정수 L과 R이 있습니다. 쿼리를 해결하기 위해 인덱스 L에서 시작하여 인덱스 R까지 하위 문자열을 사용합니다. 그리고 하위 문자열에서 반복되지 않는 마지막 문자를 찾습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :str ="튜토리얼 포인트" Q =2

쿼리 ={{4, 8}, {2, 6}}

출력 :-1 , -1

설명

subStr[4...8] ="리알". 반복되지 않는 마지막 문자는 s입니다. 그러나 모든 문자의 빈도는 1입니다.

subStr[2...6] ="토리아". 반복되지 않는 마지막 문자는 입니다. 그러나 모든 문자의 빈도는 1입니다.

해결 방법

문제를 해결하려면 단일 발생 빈도를 가진 문자를 찾아야 합니다. 이를 위해 쉽고 간단한 접근 방식은 charFreq[][]를 계산하는 행렬을 만드는 것입니다. 하위 배열 쿼리를 해결하기 위해 모든 문자의 발생 빈도를 확인하고 빈도가 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