Untitled

mail@pastecode.io avatar
unknown
plain_text
20 days ago
1.3 kB
3
Indexable
Never
// Online C++ compiler to run C++ program online
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(vector<int> count){
    int totalOdd = 0;
    for(int i=0; i<26;i++){
        if(count[i]&1){
            totalOdd++;
        }
    }
    return totalOdd<2;
}

vector<int> subtract(vector<int> count, vector<int> second){
    vector<int> ans(26,0);
    for(int i=0; i<26;i++){
        ans[i] = count[i]-second[i];
    }
    return ans;
}

bool canMakePalindrome(string& s, int len, vector<vector<int>> count){
    int n = s.size();
    for(int i=len;i<n;i++){
        int j = i-len;
        vector<int> final = subtract(count[n],subtract(count[i+1],count[i+1-len]));
        if(isPalindrome(final)){
            return true;
        }
    }
    return false;
}
int getMinSubstring(string s){
    int n = s.size();
    vector<vector<int>> count(n+1,vector<int>(26,0));
    vector<int> curr(26,0);
    for(int i=0; i<n;i++){
        curr[s[i]-'a']++;
        count[i+1] = curr;
    }
    int ans = 0;
    for(int len=1; len<n;len++){
        if(canMakePalindrome(s,len,count)){
            return len;
        }
    }
    
    return ans;
}


int main() {
    // Write C++ code here
    std::cout << getMinSubstring("abcdc");
    
    return 0;
}
Leave a Comment