C++で指定された文字列のサブ文字列内の最後の非反復文字を検索するためのクエリ

この問題では、文字列strとQクエリが与えられ、それぞれが2つの整数で構成されています。私たちのタスクは、クエリを解決して、C++で指定された文字列のサブ文字列内の最後の繰り返しのない文字を見つけるプログラムを作成することです。

問題の説明

各クエリには、2つの整数LとRがあります。クエリを解決するために、インデックスLからインデックスRまでのサブストリングを取得し、サブストリング内で繰り返されない最後の文字を見つけます。

問題を理解するために例を見てみましょう

入力 ：str =“ Tutorialspoint” Q =2

クエリ={{4、8}、{2、6}}

出力 ：-1、-1

説明

subStr [4 ... 8] =“ rials”。最後の繰り返されない文字はsです。ただし、すべての文字の頻度は1です。

subStr [2 ... 6] =“ toria”。最後の繰り返されない文字はです。ただし、すべての文字の頻度は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