本文概述
给定一个字符串str对于小写字符, 任务是删除重复项并返回结果字符串, 而无需修改原始字符串中字符的顺序。
例子:
Input: str = "lsbinforlsbin"
Output: lsbinfor
Input: str = "characters"
Output: chartes
方法:这个想法是使用计数器变量以标记字符串中是否存在字符。要标记" a"的存在, 请将第0位设置为1, 为" b"将第1位设置为1, 依此类推。如果原始字符串中存在的字符的相应位设置为0, 则表示它是该字符的首次出现, 因此将其相应位设置为1, 并继续在结果字符串中包括当前字符。
考虑字符串str =" lsbinforlsbin"
字符:'g'
x = 6(g – 97的ascii)计数器中的第6位未设置, 导致首次出现字符'g'。
str [0] ='g'
计数器= 00000000000000000000000001000000 //将第6位标记为已访问
长度= 1
字符:'e'
x = 4(e – 97的ascii)
计数器中的第4位未设置, 导致首次出现字符'e '。
str [1] =‘e’
计数器= 00000000000000000000000001010000 //将第4位标记为已访问
长度= 2
字符:‘e’
x = 4(e – 97的ascii)
设置计数器的第4位将导致重复字符。
忽略此字符。移动到下一个字符。
计数器= 00000000000000000000000001010000 //与先前的
长度= 2
字符相同:'k'
x = 10(k的ascii – 97)计数器中的第10位未设置, 导致首次出现字符'k'。
str [2] ='k'
计数器= 00000000000000000000010001010000 //将第10位标记为已访问
长度= 3
类似地, 对所有字符都执行相同的操作。
结果字符串:lsbinfor(从索引0开始的长度为7的字符串)
算法:
- 初始化一个计数器变量(保持跟踪字符串中访问的字符), 它是一个32位整数, 最初表示为(00000000000000000000000000000000)。
- 假设" a"为计数器的第0位, " b"为计数器的第1位, " c"为计数器的第2位, 依此类推。
- 遍历输入字符串的每个字符。
- 获取角色的值, 其中角色的值(x)=角色的Ascii –97。这将确保将'a'的值设置为0, 将'b'的值设置为1, 依此类推。
- 检查计数器的第x位。
- 如果计数器的第X位为0, 则表示当前字符是第一次出现, 请将当前字符保留在string的"长度"索引处。
- 通过设置计数器的第x位来标记当前访问的字符。
- 增量长度。
- 从索引0返回大小为"长度"的子字符串。
下面是上述方法的实现:
C ++
// C++ implementation of above approach
#include <bits/stdc++.h>
#include <string>
using namespace std;
// Function to remove duplicates
string removeDuplicatesFromString(string str)
{
// keeps track of visited characters
int counter = 0;
int i = 0;
int size = str.size();
// gets character value
int x;
// keeps track of length of resultant string
int length = 0;
while (i < size) {
x = str[i] - 97;
// check if Xth bit of counter is unset
if ((counter & (1 << x)) == 0) {
str[length] = 'a' + x;
// mark current character as visited
counter = counter | (1 << x);
length++;
}
i++;
}
return str.substr(0, length);
}
// Driver code
int main()
{
string str = "lsbinforlsbin" ;
cout << removeDuplicatesFromString(str);
return 0;
}
Java
// Java implementation of above approach
import java.util.Arrays;
class GFG {
// Function to remove duplicates
static char [] removeDuplicatesFromString(String string)
{
// keeps track of visited characters
int counter = 0 ;
char [] str = string.toCharArray();
int i = 0 ;
int size = str.length;
// gets character value
int x;
// keeps track of length of resultant String
int length = 0 ;
while (i < size) {
x = str[i] - 97 ;
// check if Xth bit of counter is unset
if ((counter & ( 1 << x)) == 0 ) {
str[length] = ( char )( 'a' + x);
// mark current character as visited
counter = counter | ( 1 << x);
length++;
}
i++;
}
return Arrays.copyOfRange(str, 0 , length);
}
// Driver code
public static void main(String[] args)
{
String str = "lsbinforlsbin" ;
System.out.println(removeDuplicatesFromString(str));
}
}
// This code is contributed by Mithun Kumar
Python3
# Python3 implementation of above approach
# Function to remove duplicates
def removeDuplicatesFromString(str2):
# keeps track of visited characters
counter = 0 ;
i = 0 ;
size = len (str2);
str1 = list (str2);
# gets character value
x = 0 ;
# keeps track of length of resultant string
length = 0 ;
while (i < size):
x = ord (str1[i]) - 97 ;
# check if Xth bit of counter is unset
if ((counter & ( 1 << x)) = = 0 ):
str1[length] = chr ( 97 + x);
# mark current character as visited
counter = counter | ( 1 << x);
length + = 1 ;
i + = 1 ;
str2 = ''.join(str1);
return str2[ 0 :length];
# Driver code
str1 = "lsbinforlsbin" ;
print (removeDuplicatesFromString(str1));
# This code is contributed by mits
C#
// C# implementation of above approach
using System;
class GFG {
// Function to remove duplicates
static string removeDuplicatesFromString( string string1)
{
// keeps track of visited characters
int counter = 0;
char [] str = string1.ToCharArray();
int i = 0;
int size = str.Length;
// gets character value
int x;
// keeps track of length of resultant String
int length = 0;
while (i < size) {
x = str[i] - 97;
// check if Xth bit of counter is unset
if ((counter & (1 << x)) == 0) {
str[length] = ( char )( 'a' + x);
// mark current character as visited
counter = counter | (1 << x);
length++;
}
i++;
}
return ( new string (str)).Substring(0, length);
}
// Driver code
static void Main()
{
string str = "lsbinforlsbin" ;
Console.WriteLine(removeDuplicatesFromString(str));
}
}
// This code is contributed by mits
的PHP
<?php
// PHP implementation of above approach
// Function to remove duplicates
function removeDuplicatesFromString( $str )
{
// keeps track of visited characters
$counter = 0;
$i = 0;
$size = strlen ( $str );
// gets character value
$x = 0;
// keeps track of length of resultant string
$length = 0;
while ( $i < $size )
{
$x = ord( $str [ $i ]) - 97;
// check if Xth bit of counter is unset
if (( $counter & (1 << $x )) == 0)
{
$str [ $length ] = chr (97 + $x );
// mark current character as visited
$counter = $counter | (1 << $x );
$length ++;
}
$i ++;
}
return substr ( $str , 0, $length );
}
// Driver code
$str = "lsbinforlsbin" ;
echo removeDuplicatesFromString( $str );
// This code is contributed by mits
?>
输出如下:
lsbinfor
时间复杂度:O(n)
空间复杂度:O(n)->由于它使用char []字符串数组来存储字符串字符(即取决于输入字符串的长度)
另一种方法:这种方法通过一个大小为256的整数数组(所有可能的字符)跟踪给定输入字符串中已访问的字符。
这个想法如下:
- 创建一个大小为256的整数数组, 以便跟踪所有可能的字符。
- 遍历输入字符串和每个字符:
- 使用ASCII码字符值作为索引:
- 如果index处的值为0, 则将字符复制到原始输入数组中并增加endIndex, 同时将index处的值更新为-1。
- 否则跳过角色。
下面是上述方法的实现:
Java
//Java implementation of above approach
import java.util.Arrays;
class GFG {
// Method to remove duplicates
static char [] removeDuplicatesFromString(String string)
{
//table to keep track of visited characters
int [] table = new int [ 256 ];
char [] chars = string.toCharArray();
//to keep track of end index of resultant string
int endIndex = 0 ;
for ( int i = 0 ; i < chars.length; i++)
{
if (table[chars[i]] == 0 )
{
table[chars[i]] = - 1 ;
chars[endIndex++] = chars[i];
}
}
return Arrays.copyOfRange(chars, 0 , endIndex);
}
// Driver code
public static void main(String[] args)
{
String str = "lsbinforlsbin" ;
System.out.println(removeDuplicatesFromString(str));
}
}
// This code is contributed by Sonu Singh
Python3
# Python3 implementation of above approach
# Method to remove duplicates
def removeDuplicatesFromString(string):
# Table to keep track of visited
# characters
table = [ 0 for i in range ( 256 )]
# To keep track of end index
# of resultant string
endIndex = 0
string = list (string)
for i in range ( len (string)):
if (table[ ord (string[i])] = = 0 ):
table[ ord (string[i])] = - 1
string[endIndex] = string[i]
endIndex + = 1
ans = ""
for i in range (endIndex):
ans + = string[i]
return ans
# Driver code
if __name__ = = '__main__' :
temp = "lsbinforlsbin"
print (removeDuplicatesFromString(temp))
# This code is contributed by Kuldeep Singh
C#
// C# implementation of above approach
using System;
class GFG
{
// Method to remove duplicates
static char [] removeDuplicatesFromString(String str)
{
// table to keep track of visited characters
int [] table = new int [256];
char [] chars = str.ToCharArray();
// to keep track of end index
// of resultant string
int endIndex = 0;
for ( int i = 0; i < chars.Length; i++)
{
if (table[chars[i]] == 0)
{
table[chars[i]] = -1;
chars[endIndex++] = chars[i];
}
}
char []newStr = new char [endIndex];
Array.Copy(chars, newStr, endIndex);
return newStr;
}
// Driver code
public static void Main(String[] args)
{
String str = "lsbinforlsbin" ;
Console.WriteLine(removeDuplicatesFromString(str));
}
}
// This code is contributed by 29AjayKumar
输出如下:
lsbinfor
时间复杂度:O(n)
空间复杂度:O(n)->由于它使用char []字符串数组来存储字符串字符(即取决于输入字符串的长度)