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

Question

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

示例：

输入： abbaabbca

输出：4

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

保证在重新排列后有回文。

有没有一种方法来解决这个问题，使用修改Manacher的或其他文本算法？

谢谢。

Answer 1

我认为标准文本处理算法的情况并非如此。这是如此简单，你不需要它们-只有一个重组的部分字符串，所以有四种情况可以发生。

1. 'ppssXXXXXXXpp'
2. 'ppXXXXXsssspp'
3. 'ppsssiiiXXXpp'
4. 'ppXXXiiissspp'

哪里

• pp是已经是回文的外部部分(可能为零)。
• XX是我们改组的一部分
• 党卫军是我们留下的一部分，它是(并改组XX匹配它)
• ii是中心周围的内部部分，也是回文(可能为零)。

我们可以先检查和剪辑外回文部分，留给我们'ssXXXXXXX'、'XXXXXssss'、'sssiiiXXX'或'XXXiiisss'。

然后我们使用对称性--如果中间部分存在，我们可以任意选择我们保留的一边，以及我们调整以适应另一边的方向，所以我们只需要选择一个。当没有中间回文部分时，我们只需运行相同的检查，但是从相反的方向开始，然后选择给出较短的子字符串的那个。

所以，让我们从一开始就开始。我们将简单地将一个字符接另一个字符's--------' 'ss-------' 'sss------'

当字符串的其余部分不再与其他字符串匹配时，停止。

那是什么时候发生的？当‘ssss.字符串的一部分已经占用了超过一半的字符出现，那么它将丢失在另一边，它不能通过洗牌来匹配。

另一方面，在传递字符串的中间部分后，我们总是会吃掉每个字符出现的一半以上。所以有三种情况可以发生。

1. 我们中间缺了。在这种情况下，我们找到了重组的字符串。'sssXXXXXXXXXXXX'
2. 我们到了中间。然后，我们也可以搜索回文的内部部分，产生类似于'ssssiiiiXXXX'的东西。
3. 有一个特殊的情况，你到达一个奇数字符串的中间-必须有一个奇数字符在那里。如果它不在那里，你将不得不像1一样继续前进。

生成的算法(在java，已经在这里试过了中)：

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

Answer 2

你可以这样用

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