Leetcode 1147. Longest Chunked Palindrome Decomposition

Posted on In ,

题目描述

You are given a string text. You should split it to k substrings (subtext1, subtext2, ..., subtextk) such that:

  • subtexti is a non-empty string.
  • The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + ... + subtextk == text).
  • subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

 

Example 1: 

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2: 

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3: 

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)".

 

Constraints:

  • 1 <= text.length <= 1000
  • text consists only of lowercase English characters.

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 * @lc app=leetcode.cn id=1147 lang=cpp
 *
 * [1147] Longest Chunked Palindrome Decomposition
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int longestDecomposition(string text) {
        int front=0,back=(text.length()-1);
        int frontptr=front,backptr=back;
        int output=0;
        while(frontptr<backptr){
            bool same=true;
            for (int i=0;i<=frontptr-front;i++){
                if (text[front+i]!=text[backptr+i])
                    same=false;
            }
            if (same){
                output+=2;
                if (backptr-1==frontptr){
                    return output;
                }
                front=++frontptr;
                back=--backptr;
            } 
            else
            {
                frontptr++;
                backptr--;
            }
        }
        return output+1;
        
    }
};

Complexity

  • Time: \(O(N^2)\)
  • Space: \(O(1)\)

题外话

The first solution is a naive solution with \(O(N^2)\) complexity. And there is a better solution, which I will try later.