找到要重新排列回文字符串的子串的最小长度
Find minimum length of substring to rearrange for palindromic string
有一个字符串s。为使字符串 s 回文而重新排列的子串的最小长度是多少。
示例:
输入: abbaabbca
输出: 4
我可以将索引 4 的子字符串重新排列为 7 (abbc),并得到 abbacabba
重排后保证有回文
有没有办法使用修改 Manacher 或其他一些文本算法来解决它?
谢谢。
你可以这样使用
bool morethanone(string s, char c)
{
// Count variable
int res = 0;
for (int i=0;i < s.length(); i++)
// checking character in string
if (s[i] == c)
res++;
if(res > 1)
return true;
else
return false;
}
int getsubstringlength(string text)
{
int result = 0;
for (int i = 0; i < text.length(); i++)
{
if(morethanone(text, text[i]))
result++;
}
return result / 2;
}
我认为标准文本处理算法并非如此。非常简单,您不需要它们 - 字符串只有一个重新洗牌的部分,因此可能会出现四种情况。
'ppssXXXXXXXpp'
'ppXXXXXsssspp'
'ppsssiiiXXXpp'
'ppXXXiiissspp'
哪里
- pp是已经回文的外层部分(可能为零)
- XX是我们重新洗牌的部分
- ss 是我们保留的部分(并重新排列 XX 以匹配它)
- ii 是围绕中心的内部也已经回文(可能为零)
我们可以先检查并剪掉外部回文部分,留下 'ssXXXXXXX'
、 'XXXXXssss'
、 'sssiiiXXX'
或 'XXXiiisss'
然后我们使用对称性——如果中间部分存在,我们可以任意选择我们保留哪一边,我们洗牌以适应另一边,所以我们只做一个。
当没有中间回文部分时,我们简单地 运行 相同的检查,但从相反的方向开始,然后我们选择给出较短子串的那个
所以,让我们从头开始。我们将简单地一个接一个地取一个字符
's--------'
'ss-------'
'sss------'
并在字符串的其余部分不再匹配时停止。
那是什么时候发生的?当字符串的'ssss...部分已经吞噬了一个字符所有出现次数的一半以上时,那么它就会在另一边丢失并且无法通过洗牌匹配。
另一方面,我们总是会在经过字符串中间后吃掉每个字符出现次数的一半以上。所以会出现三种情况。
- 我们 运行 离中间不远。在这种情况下,我们找到了要重新洗牌的字符串。
'sssXXXXXXXXXXXX'
- 我们到了中间。然后我们也可以搜索回文的内部部分,产生类似于
'ssssiiiiXXXX'
- 有一种特殊情况,您到达奇数边字符串的中间 - 那里必须有一个奇数个字符。如果不存在,您将必须按照 1)
进行操作
生成的算法(在 java、already tried it here 中):
package palindrometest;
import java.io.*;
import java.util.*;
import java.util.stream.*;
class PalindromeTest {
static int[] findReshuffleRange( String s ) {
// first the easy part,
//split away the already palindromatic start and end if there is any
int lo = 0, hi = s.length()-1;
while(true) {
if( lo >= hi ) {
return new int[]{0,0}; // entire string a palindrome
}
if( s.charAt(lo) != s.charAt(hi) ) {
break;
}
lo++;
hi--;
}
// now we compute the char counts and things based on them
Map<Character,Integer> charCounts = countChars( s, lo, hi );
if( !palindromePossible( charCounts ) ) {
return null;
}
Map<Character,Integer> halfCounts = halfValues( charCounts );
char middleChar = 0;
if( (s.length() % 2) != 0 ) { // only an odd-sized string has a middle char
middleChar = findMiddleChar( charCounts );
}
// try from the beginning first
int fromStart[] = new int[2];
if( findMiddlePart( fromStart, s, lo, hi, halfCounts, middleChar, false ) ) {
// if the middle palindromatic part exist, the situation is symmetric
// we don't have to check the opposite direction
return fromStart;
}
// try from the end
int fromEnd[] = new int[2];
findMiddlePart( fromEnd, s, lo, hi, halfCounts, middleChar, true );
// take the shorter
if( fromEnd[1]-fromEnd[0] < fromStart[1]-fromStart[0] ) {
return fromEnd;
} else {
return fromStart;
}
}
static boolean findMiddlePart( int[] result, String s, int lo, int hi, Map<Character,Integer> halfCounts, char middleChar, boolean backwards ) {
Map<Character,Integer> limits = new HashMap<>(halfCounts);
int pos, direction, end, oth;
if( backwards ) {
pos = hi;
direction = -1;
end = (lo+hi)/2; // mid rounded down
oth = (lo+hi+1)/2; // mid rounded up
} else {
pos = lo;
direction = 1;
end = (lo+hi+1)/2; // mid rounded up
oth = (lo+hi)/2; // mid rounded down
}
// scan until we run out of the limits
while(true) {
char c = s.charAt(pos);
int limit = limits.get(c);
if( limit <= 0 ) {
break;
}
limits.put(c,limit-1);
pos += direction;
}
// whether we reached the middle
boolean middleExists = pos == end && ( oth != end || s.charAt(end) == middleChar );
if( middleExists ) {
// scan through the middle until we find the first non-palindromic character
while( s.charAt(pos) == s.charAt(oth) ) {
pos += direction;
oth -= direction;
}
}
// prepare the resulting interval
if( backwards ) {
result[0] = lo;
result[1] = pos+1;
} else {
result[0] = pos;
result[1] = hi+1;
}
return middleExists;
}
static Map<Character,Integer> countChars( String s, int lo, int hi ) {
Map<Character,Integer> charCounts = new HashMap<>();
for( int i = lo ; i <= hi ; i++ ) {
char c = s.charAt(i);
int cnt = charCounts.getOrDefault(c,0);
charCounts.put(c,cnt+1);
}
return charCounts;
}
static boolean palindromePossible(Map<Character,Integer> charCounts) {
int oddCnt = 0;
for( int cnt : charCounts.values() ) {
if( (cnt % 2) != 0 ) {
oddCnt++;
if( oddCnt > 1 ) {
return false; // can not be made palindromic
}
}
}
return true;
}
static char findMiddleChar( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
if( (cnt % 2) != 0 ) {
return c;
}
}
return 0;
}
static Map<Character,Integer> halfValues( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
halfCounts.put(c,cnt/2); // we round *down*
}
return halfCounts;
}
static String repeat(char c, int cnt ) {
return cnt <= 0 ? "" : String.format("%"+cnt+"s","").replace(" ",""+c);
}
static void testReshuffle(String s ) {
int rng[] = findReshuffleRange( s );
if( rng == null ) {
System.out.println("Result : '"+s+"' is not palindromizable");
} else if( rng[0] == rng[1] ) {
System.out.println("Result : whole '"+s+"' is a palindrome");
} else {
System.out.println("Result : '"+s+"'");
System.out.println(" "+repeat('-',rng[0])+repeat('X',rng[1]-rng[0])+repeat('-',s.length()-rng[1]) );
}
}
public static void main (String[] args) {
testReshuffle( "abcdefedcba" );
testReshuffle( "abcdcdeeba" );
testReshuffle( "abcfdeedcba" );
testReshuffle( "abcdeedbca" );
testReshuffle( "abcdefcdeba" );
testReshuffle( "abcdefgfcdeba" );
testReshuffle( "accdefcdeba" );
}
}
有一个字符串s。为使字符串 s 回文而重新排列的子串的最小长度是多少。
示例:
输入: abbaabbca
输出: 4
我可以将索引 4 的子字符串重新排列为 7 (abbc),并得到 abbacabba
重排后保证有回文
有没有办法使用修改 Manacher 或其他一些文本算法来解决它?
谢谢。
你可以这样使用
bool morethanone(string s, char c)
{
// Count variable
int res = 0;
for (int i=0;i < s.length(); i++)
// checking character in string
if (s[i] == c)
res++;
if(res > 1)
return true;
else
return false;
}
int getsubstringlength(string text)
{
int result = 0;
for (int i = 0; i < text.length(); i++)
{
if(morethanone(text, text[i]))
result++;
}
return result / 2;
}
我认为标准文本处理算法并非如此。非常简单,您不需要它们 - 字符串只有一个重新洗牌的部分,因此可能会出现四种情况。
'ppssXXXXXXXpp'
'ppXXXXXsssspp'
'ppsssiiiXXXpp'
'ppXXXiiissspp'
哪里
- pp是已经回文的外层部分(可能为零)
- XX是我们重新洗牌的部分
- ss 是我们保留的部分(并重新排列 XX 以匹配它)
- ii 是围绕中心的内部也已经回文(可能为零)
我们可以先检查并剪掉外部回文部分,留下 'ssXXXXXXX'
、 'XXXXXssss'
、 'sssiiiXXX'
或 'XXXiiisss'
然后我们使用对称性——如果中间部分存在,我们可以任意选择我们保留哪一边,我们洗牌以适应另一边,所以我们只做一个。 当没有中间回文部分时,我们简单地 运行 相同的检查,但从相反的方向开始,然后我们选择给出较短子串的那个
所以,让我们从头开始。我们将简单地一个接一个地取一个字符
's--------'
'ss-------'
'sss------'
并在字符串的其余部分不再匹配时停止。
那是什么时候发生的?当字符串的'ssss...部分已经吞噬了一个字符所有出现次数的一半以上时,那么它就会在另一边丢失并且无法通过洗牌匹配。
另一方面,我们总是会在经过字符串中间后吃掉每个字符出现次数的一半以上。所以会出现三种情况。
- 我们 运行 离中间不远。在这种情况下,我们找到了要重新洗牌的字符串。
'sssXXXXXXXXXXXX'
- 我们到了中间。然后我们也可以搜索回文的内部部分,产生类似于
'ssssiiiiXXXX'
- 有一种特殊情况,您到达奇数边字符串的中间 - 那里必须有一个奇数个字符。如果不存在,您将必须按照 1) 进行操作
生成的算法(在 java、already tried it here 中):
package palindrometest;
import java.io.*;
import java.util.*;
import java.util.stream.*;
class PalindromeTest {
static int[] findReshuffleRange( String s ) {
// first the easy part,
//split away the already palindromatic start and end if there is any
int lo = 0, hi = s.length()-1;
while(true) {
if( lo >= hi ) {
return new int[]{0,0}; // entire string a palindrome
}
if( s.charAt(lo) != s.charAt(hi) ) {
break;
}
lo++;
hi--;
}
// now we compute the char counts and things based on them
Map<Character,Integer> charCounts = countChars( s, lo, hi );
if( !palindromePossible( charCounts ) ) {
return null;
}
Map<Character,Integer> halfCounts = halfValues( charCounts );
char middleChar = 0;
if( (s.length() % 2) != 0 ) { // only an odd-sized string has a middle char
middleChar = findMiddleChar( charCounts );
}
// try from the beginning first
int fromStart[] = new int[2];
if( findMiddlePart( fromStart, s, lo, hi, halfCounts, middleChar, false ) ) {
// if the middle palindromatic part exist, the situation is symmetric
// we don't have to check the opposite direction
return fromStart;
}
// try from the end
int fromEnd[] = new int[2];
findMiddlePart( fromEnd, s, lo, hi, halfCounts, middleChar, true );
// take the shorter
if( fromEnd[1]-fromEnd[0] < fromStart[1]-fromStart[0] ) {
return fromEnd;
} else {
return fromStart;
}
}
static boolean findMiddlePart( int[] result, String s, int lo, int hi, Map<Character,Integer> halfCounts, char middleChar, boolean backwards ) {
Map<Character,Integer> limits = new HashMap<>(halfCounts);
int pos, direction, end, oth;
if( backwards ) {
pos = hi;
direction = -1;
end = (lo+hi)/2; // mid rounded down
oth = (lo+hi+1)/2; // mid rounded up
} else {
pos = lo;
direction = 1;
end = (lo+hi+1)/2; // mid rounded up
oth = (lo+hi)/2; // mid rounded down
}
// scan until we run out of the limits
while(true) {
char c = s.charAt(pos);
int limit = limits.get(c);
if( limit <= 0 ) {
break;
}
limits.put(c,limit-1);
pos += direction;
}
// whether we reached the middle
boolean middleExists = pos == end && ( oth != end || s.charAt(end) == middleChar );
if( middleExists ) {
// scan through the middle until we find the first non-palindromic character
while( s.charAt(pos) == s.charAt(oth) ) {
pos += direction;
oth -= direction;
}
}
// prepare the resulting interval
if( backwards ) {
result[0] = lo;
result[1] = pos+1;
} else {
result[0] = pos;
result[1] = hi+1;
}
return middleExists;
}
static Map<Character,Integer> countChars( String s, int lo, int hi ) {
Map<Character,Integer> charCounts = new HashMap<>();
for( int i = lo ; i <= hi ; i++ ) {
char c = s.charAt(i);
int cnt = charCounts.getOrDefault(c,0);
charCounts.put(c,cnt+1);
}
return charCounts;
}
static boolean palindromePossible(Map<Character,Integer> charCounts) {
int oddCnt = 0;
for( int cnt : charCounts.values() ) {
if( (cnt % 2) != 0 ) {
oddCnt++;
if( oddCnt > 1 ) {
return false; // can not be made palindromic
}
}
}
return true;
}
static char findMiddleChar( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
if( (cnt % 2) != 0 ) {
return c;
}
}
return 0;
}
static Map<Character,Integer> halfValues( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
halfCounts.put(c,cnt/2); // we round *down*
}
return halfCounts;
}
static String repeat(char c, int cnt ) {
return cnt <= 0 ? "" : String.format("%"+cnt+"s","").replace(" ",""+c);
}
static void testReshuffle(String s ) {
int rng[] = findReshuffleRange( s );
if( rng == null ) {
System.out.println("Result : '"+s+"' is not palindromizable");
} else if( rng[0] == rng[1] ) {
System.out.println("Result : whole '"+s+"' is a palindrome");
} else {
System.out.println("Result : '"+s+"'");
System.out.println(" "+repeat('-',rng[0])+repeat('X',rng[1]-rng[0])+repeat('-',s.length()-rng[1]) );
}
}
public static void main (String[] args) {
testReshuffle( "abcdefedcba" );
testReshuffle( "abcdcdeeba" );
testReshuffle( "abcfdeedcba" );
testReshuffle( "abcdeedbca" );
testReshuffle( "abcdefcdeba" );
testReshuffle( "abcdefgfcdeba" );
testReshuffle( "accdefcdeba" );
}
}