在C ++中查找给定字符串的子字符串中最后一个非重复字符的查询

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们给了字符串str和Q查询，每个查询由两个整数组成。我们的任务是创建一个程序来解决查询，以在C ++中找到给定字符串的子字符串中的最后一个非重复字符。

问题描述

在每个查询中，我们都有两个整数L和R。为解决查询，我们将从索引L到索引R取一个子字符串。并在该子字符串中找到不重复的最后一个字符。

让我们举个例子来了解这个问题，

输入：str =“ Nhooo” Q = 2

查询= {{4，8}，{2，6}}

输出：-1，-1

说明

subStr [4 ... 8] =“里亚尔”。最后一个非重复字符是s。但是所有字符的频率均为1。

subStr [2 ... 6] =“ toria”。最后一个非重复字符是a。但是所有字符的频率均为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 = "nhooo";
   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

以上是 在C ++中查找给定字符串的子字符串中最后一个非重复字符的查询 的全部内容， 来源链接： utcz.com/z/360888.html

回到顶部