找到要重新排列回文字符串的子串的最小长度

Question

有一个字符串s。为使字符串 s 回文而重新排列的子串的最小长度是多少。

示例：

输入： abbaabbca

输出： 4

我可以将索引 4 的子字符串重新排列为 7 (abbc)，并得到 abbacabba

重排后保证有回文

有没有办法使用修改 Manacher 或其他一些文本算法来解决它？

谢谢。

Answer 1

你可以这样使用

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;
}

Answer 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" );
    }
}

找到要重新排列回文字符串的子串的最小长度

Find minimum length of substring to rearrange for palindromic string

c++

palindrome