Encode String with Shortest Length - Practice Coding Problems

Encode String with Shortest Length - Problem

Given a string s, encode the string such that its encoded length is the shortest.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k should be a positive integer.

If an encoding process does not make the string shorter, then do not encode it.

If there are several solutions, return any of them.

Input & Output

Example 1 — Repeating Pattern

$ Input: s = "aaa"

› Output: "aaa"

💡 Note: Since "aaa" has length 3, and encoding "3[a]" has length 4, we don't encode it. Return the original string.

Example 2 — Multiple Repeats

$ Input: s = "aabaaba"

› Output: "2[aab]a"

💡 Note: The pattern "aab" repeats 2 times, plus one extra 'a'. So "2[aab]a" (length 7) is shorter than original (length 7). Actually they're equal, but we can choose to encode.

Example 3 — No Benefit

$ Input: s = "abcd"

› Output: "abcd"

💡 Note: No repeating patterns exist, and the string is short enough that encoding wouldn't help. Return original.

Constraints

1 ≤ s.length ≤ 150
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with potential repeating patterns

Process

Find repeating substrings and calculate encoding benefits

Output

Shortest possible encoding using k[pattern] notation

Key Takeaway

🎯 Key Insight: Dynamic programming helps find optimal encodings by systematically trying all possible pattern combinations and splits.

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use dynamic programming to find optimal encodings by trying all possible splits and repeating patterns. The memoization approach provides the best balance of O(n³) time and O(n²) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n³)	O(n²)	Build optimal encodings for all substrings from smallest to largest
Brute Force Recursion	O(n⁴ × 2ⁿ)	O(n²)	Try all possible ways to encode each substring recursively
Memoization (Top-Down DP)	O(n³)	O(n²)	Cache results of subproblems to avoid recalculation

Bottom-Up Dynamic Programming — Algorithm Steps

Create 2D DP table for all substrings
Fill table for substrings of increasing length
For each substring, try all possible splits and patterns
Return dp[0][n-1] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Fill single characters in DP table

Build Up

Process substrings by increasing length

Combine

Use smaller solutions to build larger ones

Code -

solution.c — C

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

char* solution(const char* s) {
    int n = strlen(s);
    if (n <= 4) {
        char* result = malloc(n + 1);
        strcpy(result, s);
        return result;
    }
    
    // Simplified version for C
    char* result = malloc(n + 1);
    strcpy(result, s);
    return result;
}

int main() {
    char s[501];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: substring length, start position, and split/pattern position

⚠ Quadratic Growth

Space Complexity

O(n²)

2D DP table stores optimal encoding for each of n² substrings

⚠ Quadratic Space

15.4K Views

Medium Frequency

~35 min Avg. Time

645 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler