Java 在O(1)额外空间中从字符串中移除重复字符

在这个问题中，我们的任务是除去字符串中除每个字符的第一次出现之外的所有重复字符。同时，要求不使用任何额外的空间来解决这个问题，空间复杂度必须为O(1)。本文使用了不同的方法来解决这个问题。其中一种方法使用布尔数组来确定字符的重复，其中布尔数组的索引与每个字母相对应。第二种方法使用位操作的概念来从结果字符串中除去重复的字符。

让我们来探索一下这篇文章，看看如何使用Java编程语言来解决它。

示例

示例1

如果字符串 = “tutorialspoint”

应用算法后 –

结果字符串 = “tuorialspn”

示例2

如果字符串 = “learningmaterial”

应用算法后 –

结果字符串 = “learnigmt”

多种方法

我们提供了不同的解决方法。

• 使用大小为26的布尔数组

• 使用单个整数位

方法1：使用大小为26的布尔数组

为了解决这个问题，我们将使用一个大小为26的布尔数组。将每个字母与布尔数组的索引相映射，以告知字符的重复。

英文字母与布尔数组的映射

'a' ⇒ found[0]
'b' ⇒ found[1]
'c' ⇒ found[2]
'd' ⇒ found[3]
.
.
.
'z' ⇒ found[25

在这里，如果found[i]= True，表示字符映射到索引-i的字符已经在字符串当前字符的左侧出现。因此，我们不再需要使用该字符。

如果found[i]= False，表示映射到索引-i的字符还没有出现，因此需要考虑它并将其插入到结果字符串中。

算法：removeDuplicatesFromStr(str)

步骤1： 创建一个名为found的数组。

步骤2： 声明一个写指针等于-1。

步骤3： 初始化for循环以遍历字符串“str”。

步骤4： 设置整数d = ASCII（str[read]）- 97。

步骤5： 如果found[d] = False，则设置found[d] = True。

步骤6： 将写指针的值增加1。

步骤7： 更新输入字符串，然后还将计算得到的字符串的最后一个字符赋值为NULL。

步骤8： 最后，打印消除冗余字符后的结果。

示例

#include <iostream>
using namespace std;
void removeDuplicatesFromStr(char inputString[]) {
   // found is a Boolean array whose index mapped to the alphabets
   bool present[26] = {false};
   // write pointer, tells the place of writing
   int write = -1;
   //use for loop 
   for (int read = 0; inputString[read] != '\0'; ++read) {
       // search bit to check character's repetition
       int d = (int)inputString[read] - 97;
       // if the character did not come yet
       if (present[d] == false) {
           present[d] = true;
           write += 1;
           inputString[write] = inputString[read];
       }
   }
   // set last character of resultant string to NULL
   inputString[write+1] = '\0';
}

int main() {
   char inputString[10000];
   int N;
   cout << "Input String for removing duplicates: ";
   cin >> inputString;
   removeDuplicatesFromStr(inputString);
   cout << "Output String after removing duplicates: " << inputString << endl;

   return 0;
}

输出

Input String for removing duplicates: learningmaterial
Output String after removing duplicates: learnigmt

程序的时间复杂度 = O(N)

程序的空间复杂度 = O(26) = O(1)

方法2：使用单个整数位

为了解决这个问题，我们创建一个整数，其位告诉我们字符是否重复。

C++中整数的大小 = 4字节 = 4*8位 = 32位。

英文字母表中的字符数 = 26

英文字母数小于整数中的位数，

因此，我们可以使用整数的各个位来表示英文字母的每个字符。

英文字母到整数的映射

'a' ⇒ bit 0 ⇒ (int)'a' - 97
'b' ⇒ bit 1 ⇒ (int)'b' - 97
'c' ⇒ bit 2 ⇒ (int)'c' - 97
'd' ⇒ bit 3 ⇒ (int)'d' - 97
.
.
.
'z' ⇒ bit 25 ⇒ (int)'z' - 97

如果字符串中有字符’a’，则bit-0变为SET。

针对每个字符执行类似的操作。

在这里，如果整数的bit-d = 1，则表示与bit-d映射的字符已经存在于字符串的当前字符的左侧。所以，我们不需要再使用那个字符了。

如果整数的bit-d = 0，则表示与bit-d映射的字符尚未出现，因此需要考虑并将其插入到结果字符串中。

算法：removeDuplicates(str)

第1步 ：创建一个名为found的整数变量。

第2步 ：声明一个写指针，初始值为-1。

第3步 ：初始化for循环以查找用于检查重复的位。

第4步 ：将整数d设置为ASCII(str[read]) – 97。

第5步 ：如果’d’不在’found’中，则将’d’插入到found中。

第6步 ：将写指针的值增加1。

第7步 ：将输入字符串进行更新，然后将计算得到的字符串的最后一个字符赋值为NULL。

第8步：最后，打印消除冗余字符后的结果。

示例

#include <iostream>
using namespace std;
void removeDuplicates(char inputStr[]) {
   // found is an integer whose bits mapped to the alphabets
   int found = 0;
   // write pointer, tells the place of writing
   int write = -1;

   for (int read = 0; inputStr[read] != '\0'; ++read) {
       // find bit for checking repetition
       int d = (int)inputStr[read] - 97;

       // if character not came yet
       if ((found & (1<<d)) == 0) {
           found = found | (1<<d);
           write += 1;
           inputStr[write] = inputStr[read];
       }
   }

   // set last character of resultant string to NULL
   inputStr[write+1] = '\0';
}

int main() {
   char inputStr[10000];
   int n;

   cout << "Input String for removing duplicates: ";
   cin >> inputStr;

   removeDuplicates(inputStr);

   cout << "Output String after removing duplicates: " << inputStr << endl;

   return 0;
}

输出

Input String for removing duplicates: tutorialspoint
Output String after removing duplicates: tuorialspn

程序的时间复杂度 = O(N)

程序的空间复杂度 = O(1)

在本文中，我们给出了两种方法来解决这个问题，时间复杂度为O(N)，空间复杂度为O(1)。