Nested Repetition Compression
Source: aizu

Nested Repetition Compression

You have a number of strings of lowercase letters to be sent in e-mails, but some of them are so long that typing as they are would be tiresome. As you found repeated parts in them, you have decided to try out a simple compression method in which repeated sequences are enclosed in parentheses, prefixed with digits meaning the numbers of repetitions. For example, the string "abababaaaaa" can be represented as "3(ab)5(a)" or "a3(ba)4(a)". The syntax of compressed representations is given below in Backus-Naur form with the start symbol $S$.

<S> ::= <R> | <R> <S>
<R> ::= <L> | <D> ( <S> )
<D> ::= 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<L> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z


Note that numbers of repetitions are specified by a single digit, and thus at most nine, but more repetitions can be specified by nesting them. A string of thirty a's can be represented as "6(5(a))" or "3(5(2(a)))", for example.

Find the shortest possible representation of the given string in this compression scheme.

Input

The input is a line containing a string of lowercase letters. The number of letters in the string is at least one and at most 200.

Output

Output a single line containing the shortest possible representation of the input string. If there exist two or more shortest representations, any of them is acceptable.

Sample Input 1
abababaaaaa

Sample Output 1
3(ab)5(a)

Sample Input 2
abababcaaaaaabababcaaaaa

Sample Output 2
2(3(ab)c5(a))

Sample Input 3
abcdefg

Sample Output 3
abcdefg


C++ solution:
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}
istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}
#endif
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define esper(...) static_cast<void>(0)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define reps(i,a,n) for(int i=(a);i<(n);i++)
#define rep(i,n) reps(i,0,n)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<x<<'\n',static_cast<void>(0)
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
void SOLVE();
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(16);
  #ifdef LOCAL
  clock_t start=clock();
  #endif
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
  #ifdef LOCAL
  cerr<<"time:";
  cerr<<(clock()-start)/1000;
  cerr<<"ms\n";
  #endif
}
void SOLVE(){
  string s;
  cin>>s;
  int n=s.size();
  vector<vector<int>>dp(n+1,vector<int>(n+1,1e9));
  for(int l=n;l>=0;l--)for(int r=l;r<=n;r++){
    dp[l][r]=r-l;
    if(r-l<=1)continue;
    reps(i,1,r-l)if((r-l)%i==0&&(r-l)/i<10){
      bool ok=true;
      reps(j,1,(r-l)/i){
        ok&=s.substr(l,i)==s.substr(l+i*j,i);
      }
      if(ok)chmin<int>(dp[l][r],dp[l][l+i]+2+to_string((r-l)/i).size());
    }
    reps(m,l+1,r)chmin(dp[l][r],dp[l][m]+dp[m][r]);
  }
  auto dfs=[&](auto self,int l,int r)->string {
    if(l==r)return "";
    if(l+1==r)return string()+s[l];
    reps(m,l+1,r)if(dp[l][r]==dp[l][m]+dp[m][r])return self(self,l,m)+self(self,m,r);
    reps(i,1,r-l)if((r-l)%i==0&&(r-l)/i<10){
      bool ok=true;
      reps(j,1,(r-l)/i){
        ok&=s.substr(l,i)==s.substr(l+i*j,i);
      }
      if(ok&&dp[l][r]==dp[l][l+i]+2+to_string((r-l)/i).size()){
        return to_string((r-l)/i)+"("+self(self,l,l+i)+")";
      }
    }
    assert(false);
  };
  cout<<dfs(dfs,0,n)<<endl;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

var memo = make(map[string]string)

func solve(s string) string {
	if len(s) <= 2 {
		return s
	}
	if cached, ok := memo[s]; ok {
		return cached
	}

	ans := s

	// Try all possible splits
	for i := 1; i < len(s); i++ {
		left := solve(s[:i])
		right := solve(s[i:])
		candidate := left + right
		if len(candidate) < len(ans) {
			ans = candidate
		}
	}

	// Try all possible repetitions (2..9)
	for k := 2; k <= 9; k++ {
		if len(s)%k != 0 {
			continue
		}
		subLen := len(s) / k
		base := s[:subLen]
		valid := true
		for i := 1; i < k; i++ {
			if s[i*subLen:(i+1)*subLen] != base {
				valid = false
				break
			}
		}
		if valid {
			compressedBase := solve(base)
			candidate := fmt.Sprintf("%d(%s)", k, compressedBase)
			if len(candidate) < len(ans) {
				ans = candidate
			}
		}
	}

	memo[s] = ans
	return ans
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	if scanner.Scan() {
		input := strings.TrimSpace(scanner.Text())
		fmt.Println(solve(input))
	}
}

Java solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    private static Map<String, String> memo = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        System.out.println(solve(s));
    }

    private static String solve(String s) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        if (s.length() <= 2) {
            memo.put(s, s);
            return s;
        }
        String ans = s;
        // Try all possible splits
        for (int i = 1; i < s.length(); i++) {
            String left = solve(s.substring(0, i));
            String right = solve(s.substring(i));
            String candidate = left + right;
            if (candidate.length() < ans.length()) {
                ans = candidate;
            }
        }
        // Try all possible repetitions (2..9)
        for (int k = 2; k <= 9; k++) {
            if (s.length() % k != 0) {
                continue;
            }
            int len = s.length() / k;
            String pattern = s.substring(0, len);
            boolean isPattern = true;
            for (int i = 1; i < k; i++) {
                if (!s.substring(i * len, (i + 1) * len).equals(pattern)) {
                    isPattern = false;
                    break;
                }
            }
            if (isPattern) {
                String compressed = k + "(" + solve(pattern) + ")";
                if (compressed.length() < ans.length()) {
                    ans = compressed;
                }
            }
        }
        memo.put(s, ans);
        return ans;
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function solve(s, memo = new Map()) {
    if (s.length <= 2) {
        return s;
    }
    if (memo.has(s)) {
        return memo.get(s);
    }

    let ans = s;

    // Try all possible splits
    for (let i = 1; i < s.length; i++) {
        const left = solve(s.substring(0, i), memo);
        const right = solve(s.substring(i), memo);
        const candidate = left + right;
        if (candidate.length < ans.length) {
            ans = candidate;
        }
    }

    // Try all possible repetitions (2..9)
    for (let k = 2; k <= 9; k++) {
        if (s.length % k !== 0) {
            continue;
        }
        const len = s.length / k;
        const pattern = s.substring(0, len);
        let isPattern = true;
        for (let i = 1; i < k; i++) {
            if (s.substring(i * len, (i + 1) * len) !== pattern) {
                isPattern = false;
                break;
            }
        }
        if (isPattern) {
            const compressed = `${k}(${solve(pattern, memo)})`;
            if (compressed.length < ans.length) {
                ans = compressed;
            }
        }
    }

    memo.set(s, ans);
    return ans;
}

rl.on('line', (input) => {
    const s = input.trim();
    console.log(solve(s));
    rl.close();
});

Python solution:
from collections import defaultdict
from functools import lru_cache
S=input()
rep_table=set()
inf = 10**9
pos = [defaultdict(list) for _ in range(len(S))]
for i in range(1,len(S)+1):
    #長さを固定
    lis = [0 for _ in range(len(S))]
    for j in range(len(S)-2*i+1,-1,-1):
        if S[j:j+i] == S[j+i:j+2*i]:
            lis[j] = max(i,lis[j+i])+(i)
            for k in range(lis[j],i,-i):
                pos[j][k].append(i)



edge = [[[] for _ in range(len(S))] for _ in range(len(S))]

@lru_cache(maxsize=10**7)
def solve(i,j):
    if i == j:
        edge[i][j] = [S[i]]
        return 1
    fle = 10**18
    fres = []
    for k in range(i+1,j+1):
        res = solve(i,k-1)
        res2 = solve(k,j)
        if res + res2 <= fle:
            fle = res + res2
            fres = [(i,k-1),(k,j)]
    for a in pos[i][j-i+1]:
        if (j-i+1)//a >= 10:
            continue
        res = solve(i,i+a-1) + 2 + len(str((j-i+1)//a))
        #print(i,j,a,'->',res)
        if res < fle:
            fle = res
            fres = [str((j-i+1)//a),"(",(i,i+a-1),")"]
    edge[i][j] = fres    
    return fle

ans = []
def make(i,j):
    for e in edge[i][j]:
        if type(e) == tuple:
            make(e[0],e[1])
        else:
            ans.append(e)

s=solve(0,len(S)-1)
make(0,len(S)-1)


print(''.join(ans))

Ruby solution:
def solve(s, memo = {})
  return memo[s] if memo.key?(s)
  
  if s.length <= 2
    memo[s] = s
    return s
  end

  ans = s

  # Try all possible splits
  (1...s.length).each do |i|
    left = solve(s[0...i], memo)
    right = solve(s[i..-1], memo)
    candidate = left + right
    if candidate.length < ans.length
      ans = candidate
    end
  end

  # Try all possible repetitions (2..9)
  (2..9).each do |k|
    next if s.length % k != 0

    len = s.length / k
    pattern = s[0, len]
    valid = true

    (1...k).each do |i|
      unless s[i * len, len] == pattern
        valid = false
        break
      end
    end

    if valid
      compressed = "#{k}(#{solve(pattern, memo)})"
      if compressed.length < ans.length
        ans = compressed
      end
    end
  end

  memo[s] = ans
  ans
end

input = gets.chomp
puts solve(input)