You have an interesting string S of length N. It is interesting because you

String Cutting Problem

You have an interesting string S of length N. It is interesting because you can rearrange the characters of this string in any order. You want to cut this string into some contiguous pieces such that after cutting, all the pieces are equal to one another.

Infosys HackWithInfy 2025

You can’t rearrange the characters in the cut pieces or join the pieces together. You want to make the number of pieces as large as possible. What is the maximum number of pieces you can get?

Note: You can observe that you may not want to cut the string at all, therefore the number of pieces is 1. Hence, the answer always exists.

Parameters:

• S :: STRING

The first line contains a string, S, denoting the string. len(S) ::  1 -> 2 * 10^5

Examples:

Case #1:

Input:

zzzzz

Output:

5

Explanation: You can cut it into 5 pieces “z” + “z” + “z” + “z” + “z”.

Case #2:

Input:

ababcc

Output:

2

Explanation: Rearrange the string as abcabc. You can cut it into “abc” + “abc”, hence the answer is 2.

Case #3:

Input:

abccdcabacda

Output:

2

Explanation: Rearrange the string as dcbaca + dcbaca, the answer is 2.

Infosys HackWithInfy 2025

Java String Cutting Code

import java.util.*;

public class StringCutting {
    public static int maxPieces(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        int gcd = 0;
        for (int f : freq) {
            if (f > 0) {
                gcd = (gcd == 0) ? f : findGCD(gcd, f);
            }
        }
        return gcd;
    }

    private static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(maxPieces("zzzzz"));
        System.out.println(maxPieces("ababcc"));
        System.out.println(maxPieces("abccdcabacda"));
    }
}
    

How the Solution Works

The key insight is that for the string to be cut into equal pieces:

• Each piece must have the same character frequency distribution
• The number of pieces must divide the frequency of each character evenly

The Algorithm:

1. First counts the frequency of each character in the string
2. Then finds the Greatest Common Divisor (GCD) of all non-zero frequencies
3. The GCD represents the maximum number of equal pieces possible

Why This Works:

If we can cut the string into k equal pieces, k must divide each character's frequency. The GCD is the largest such number that divides all frequencies. This guarantees that we can rearrange the string to form that many equal pieces.

Complexity:

Time complexity: O(n + 26 * log m), where n is the string length and m is the maximum frequency of any character.

Space complexity: O(1) since we use a fixed-size array of 26 characters.

Infosys HackWithInfy 2025

Python Code Example

This is a Python function that calculates the maximum number of pieces based on character frequency.

from collections import Counter
from math import gcd
from functools import reduce

def max_pieces(s: str) -> int:
    # Count frequency of each character
    freq = Counter(s)
    
    # Get all non-zero frequencies
    frequencies = list(freq.values())
    
    # Find GCD of all frequencies using reduce
    return reduce(gcd, frequencies)

# Test cases
def run_tests():
    test_cases = [
        "zzzzz",          # Should return 5
        "ababcc",         # Should return 2
        "abccdcabacda"    # Should return 2
    ]
    
    for test in test_cases:
        result = max_pieces(test)
        print(f"Input: {test}")
        print(f"Output: {result}\n")

if __name__ == "__main__":
    run_tests()
    

Python Solution Explanation

This Python solution is actually more concise than the Java version, thanks to Python's built-in tools. Let me explain the key components:

• Counter from collections to count character frequencies
• gcd from math module for Greatest Common Divisor calculations
• reduce from functools to apply gcd across all frequencies

The algorithm remains the same:

1. Count frequencies of all characters
2. Find the GCD of all frequencies
3. The GCD represents the maximum number of equal pieces possible

Key differences from Java version:

• No need for explicit character array handling
• Built-in GCD function instead of implementing our own
• More pythonic syntax and structure

Time complexity: O(n + k*log m) where:

• n is the string length (for counting frequencies)
• k is the number of unique characters
• m is the maximum frequency

Space complexity: O(k) where k is the number of unique characters in the string.

Infosys HackWithInfy 2025

C Code Example

This is a C program that calculates the maximum number of equal pieces of characters in a string by finding the GCD of character frequencies:

#include <stdio.h>
#include <string.h>

// Function to find GCD of two numbers
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Function to find GCD of array of numbers
int find_array_gcd(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] != 0) {  // Skip zero frequencies
            result = gcd(result, arr[i]);
        }
    }
    return result;
}

// Main function to find maximum number of equal pieces
int max_pieces(const char* s) {
    // Array to store frequency of each character (assuming lowercase letters only)
    int freq[26] = {0};
    int len = strlen(s);
    
    // Count frequency of each character
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    // Find first non-zero frequency
    int first_non_zero = 0;
    while (first_non_zero < 26 && freq[first_non_zero] == 0) {
        first_non_zero++;
    }
    
    if (first_non_zero == 26) return 1;  // Empty string or invalid input
    
    // Initialize result with first non-zero frequency
    int result = freq[first_non_zero];
    
    // Find GCD of all non-zero frequencies
    for (int i = first_non_zero + 1; i < 26; i++) {
        if (freq[i] > 0) {
            result = gcd(result, freq[i]);
        }
    }
    
    return result;
}

int main() {
    // Test cases
    const char* test_cases[] = {
        "zzzzz",
        "ababcc",
        "abccdcabacda"
    };
    int num_tests = 3;
    
    for (int i = 0; i < num_tests; i++) {
        printf("Input: %s\n", test_cases[i]);
        printf("Output: %d\n\n", max_pieces(test_cases[i]));
    }
    
    return 0;
}
    

Infosys HackWithInfy 2025

C Implementation Explanation

The C solution follows the same logic as the Python and Java versions, but with some C-specific considerations:

• Uses array instead of HashMap/Counter for character frequency
• Manual memory management and array handling
• More explicit error handling for edge cases
• Direct pointer manipulation for string processing

The algorithm breaks down into three main functions:

• gcd: Calculates GCD of two numbers using Euclidean algorithm
• find_array_gcd: Finds GCD of an array of numbers (unused in final version but kept for potential future use)
• max_pieces: Main function that processes the string and finds the solution

Important C-specific considerations:

• Uses fixed-size array for frequencies (26 for lowercase letters)
• Manual string length calculation using strlen()
• Careful handling of zero frequencies
• No dynamic memory allocation needed for this solution

Time Complexity

Time complexity: O(n + 26*log m) where:

• n is the string length (for counting frequencies)
• m is the maximum frequency value
• The 26 factor comes from iterating through the frequency array

Space Complexity

Space complexity: O(1) since we use a fixed-size array of 26 characters.

C++ Code Example

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <numeric>
using namespace std;

class StringCutter {
private:
    // Helper function to find GCD of two numbers using C++'s standard library
    int findGCD(int a, int b) {
        return gcd(a, b);  // Using C++17's std::gcd
    }

    // Helper function to find GCD of a vector of numbers
    int findArrayGCD(const vector<int>& numbers) {
        if (numbers.empty()) return 0;
        
        int result = numbers[0];
        for (size_t i = 1; i < numbers.size(); i++) {
            result = findGCD(result, numbers[i]);
        }
        return result;
    }

public:
    int maxPieces(const string& s) {
        // Use unordered_map for frequency counting
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        // Extract non-zero frequencies into a vector
        vector<int> frequencies;
        for (const auto& [ch, count] : freq) {
            if (count > 0) {
                frequencies.push_back(count);
            }
        }
        
        // Find GCD of all frequencies
        return findArrayGCD(frequencies);
    }
};

// Function to run test cases
void runTests() {
    vector<string> testCases = {
        "zzzzz",
        "ababcc",
        "abccdcabacda"
    };
    
    StringCutter solver;
    
    for (const string& test : testCases) {
        cout << "Input: " << test << "\n";
        cout << "Output: " << solver.maxPieces(test) << "\n\n";
    }
}

int main() {
    runTests();
    return 0;
}
    

C++ Solution Improvements

Modern C++ Features Used:

• Classes and object-oriented design
• STL containers (unordered_map, vector)
• Range-based for loops
• Auto type deduction
• Structured bindings (C++17)
• std::gcd from numeric library (C++17)

Key Improvements:

• More robust error handling through C++ containers
• Better encapsulation using class design
• More efficient string handling using std::string
• Automatic memory management
• Type safety improvements

Algorithm Remains the Same but with C++ Optimizations:

• Use unordered_map instead of fixed array for frequency counting
• Vector for dynamic storage of non-zero frequencies
• Built-in GCD function from C++17's numeric library

Time Complexity:

O(n + k*log m) where:

• n is the string length
• k is the number of unique characters
• m is the maximum frequency

Space Complexity:

O(k) where k is the number of unique characters.

Infosys HackWithInfy 2025