#43Medium~35 min

Multiply Strings

Time O(m * n) · Space O(m + n) · Official statement on LeetCode

Solutions

// Time:  O(m * n)
// Space: O(m + n)

class Solution {
public:
    string multiply(string num1, string num2) {
        string result(num1.size() + num2.size(), '0');
        for (int i = num1.size() - 1; i >= 0; --i) {
            for (int j = num2.size() - 1; j >= 0; --j) {
                int sum = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0');
                result[i + j + 1] = sum % 10 + '0';
                result[i + j] += sum / 10;
            }
        }
        int pos = result.find_first_not_of('0');
        if (pos != string::npos) {
            return result.substr(pos);
        }
        return "0";
    }
};

// Time:  O(m * n)
// Space: O(m + n)
class Solution2 {
public:
    string multiply(string num1, string num2) {
        const auto char_to_int = [](const char c) { return c - '0'; };
        const auto int_to_char = [](const int i) { return i + '0'; };

        vector<int> n1;
        transform(num1.rbegin(), num1.rend(), back_inserter(n1), char_to_int);
        vector<int> n2;
        transform(num2.rbegin(), num2.rend(), back_inserter(n2), char_to_int);

        vector<int> tmp(n1.size() + n2.size());
        for(int i = 0; i < n1.size(); ++i) {
            for(int j = 0; j < n2.size(); ++j) {
                tmp[i + j] += n1[i] * n2[j];
                tmp[i + j + 1] += tmp[i + j] / 10;
                tmp[i + j] %= 10;
            }
        }
            
        string res;
        transform(find_if(tmp.rbegin(), prev(tmp.rend()),
                         [](const int i) { return i != 0; }),
                  tmp.rend(), back_inserter(res), int_to_char);
        return res;
    }
};

// Time:  O(m * n)
// Space: O(m + n)
// Define a new BigInt class solution. 
class Solution3 {
public:
    string multiply(string num1, string num2) {
        return BigInt(num1) * BigInt(num2);
    }

    class BigInt {
    public:
        BigInt(const string& s) {
            transform(s.rbegin(), s.rend(), back_inserter(n_), 
                      [](const char c) { return c - '0'; });
        }
    
        operator string() {
            string s;
            transform(find_if(n_.rbegin(), prev(n_.rend()),
                             [](const int i) { return i != 0; }),
                      n_.rend(), back_inserter(s), 
                      [](const int i) { return i + '0'; });
            return s;
        }
    
        BigInt operator*(const BigInt &rhs) const {
            BigInt res(n_.size() + rhs.size(), 0);
            for(auto i = 0; i < n_.size(); ++i) {
                for(auto j = 0; j < rhs.size(); ++j) {
                    res[i + j] += n_[i] * rhs[j];
                    res[i + j + 1] += res[i + j] / 10;
                    res[i + j] %= 10;
                }
            }
            return res;
        }
    
    private:
        vector<int> n_;
    
        BigInt(int num, int val): n_(num, val) {
        }
    
        // Getter.
        int operator[] (int i) const {
            return n_[i];
        }
    
        // Setter.
        int & operator[] (int i) {
            return n_[i];
        }
    
        size_t size() const {
            return n_.size();
        }
    };
};

Beginner Explanation

What is Multiply Strings?

Multiply Strings (LeetCode #43) is a Medium problem that primarily trains string.

How to think about it

Restate the goal in your own words before coding.
Work a tiny example by hand so the invariant becomes obvious.
Identify the pattern — this problem aligns with general problem-solving.
Only then translate the idea into code.

Why this problem matters

It sits in the sweet spot of interview difficulty: multiple valid approaches, clear trade-offs.

AlgoForge explanations are original teaching notes. Always open the official problem statement on LeetCode for constraints and examples.

Interview Walkthrough

Interview approach for Multiply Strings

Opening (30–60 seconds)

Clarify inputs/outputs and edge cases (empty input, single element, duplicates, overflow).
State a brute force so the interviewer knows you can solve it naively.
Propose the optimal direction tied to general problem-solving.

Core solution narrative

Define the state you track (pointers, DP cell, set membership, stack top, etc.).
Explain the transition when you process the next element.
Call out time (O(m * n)) and space (O(m + n)) before coding.
Code cleanly; narrate variable names.

What interviewers listen for

Correctness on edge cases
Complexity honesty
Ability to discuss trade-offs (e.g., hash map space vs. sort + two pointers)

Follow-up questions they may ask

Can you solve it with less memory?
What if the input stream is infinite / doesn't fit in RAM?
How would tests look for adversarial inputs?

Optimized Approach

Optimized solution notes

The reference solutions on AlgoForge target O(m * n) time and O(m + n) space.

Pattern focus: general problem-solving

Use the pattern as a checklist:

Identify the dominant pattern and stick to one clear invariant

Multiple methods appear in the source solutions — compare them and explain when each is preferable.

Implementation tips

Prefer readable names over micro-optimizations in interviews.
Extract helpers only when they clarify (e.g., expand-around-center, DFS visit).
After AC-level logic, re-scan for off-by-one and null checks.

Complexity Analysis

Complexity

Measure	Bound
Time	*O(m n)**
Space	O(m + n)

How to justify this in an interview

Time: count loops, map/set operations, and recursive branching; state average vs worst case if relevant.
Space: include hash maps, recursion stack, and output allocation when the problem asks for it.

If your implementation differs from the reference, re-derive big-O from your code — never memorize a complexity you cannot defend.

Common Mistakes

Common mistakes on Multiply Strings

Skipping edge cases — empty collections, single-element inputs, max constraints.
Wrong invariant for general problem-solving — updating state too early or too late.
Mutating input unexpectedly when the problem forbids it.
Off-by-one in windows, ranges, or binary search bounds.
Ignoring overflow / precision for integer arithmetic problems.
Overengineering — jumping to an advanced structure when a simpler approach works.

Alternative Approaches

Alternatives

The source file includes more than one method. Compare:

Primary optimized path — best complexity for typical interviews.
Secondary approach — often brute force, sorting-based, or space-optimized variant.

Practice articulating when you would pick each (constraints, readability, follow-ups).

Edge Cases

Edge cases checklist

Minimum input size
Maximum input size / time limits
Duplicates and already-sorted input
Negative numbers / zeros (if applicable)
Disconnected structures (graphs/trees)
Single path vs branching recursion depth

Pattern Recognition

Spotting this pattern

Signal phrases that point to general problem-solving:

Sorted input or ability to sort without changing the answer class
Need for contiguous subarray / substring → consider sliding window
Need for O(1) membership → hash set/map
Optimal substructure + overlapping subproblems → DP
Connectivity / components → graph DFS/BFS or Union-Find

Primary topics: string.

Follow-up Interview Questions

Follow-ups

How does the solution change if the input is a stream?
Can you solve it in-place?
What if duplicates must be handled differently?
How would you parallelize the approach?
Design tests that would break a buggy implementation.

Practice Recommendations

What to practice next

Re-solve Multiply Strings in a second language (cpp, python).
Drill 3–5 more problems tagged string.
Teach the solution out loud in under 5 minutes.
Add this problem to your revision calendar in 3 days and 14 days.

Visualization

Conceptual diagram for Multiply Strings: show input structure (string), highlight the moving parts of the general problem-solving approach, and annotate each step with the maintained invariant and complexity.

Study checklist

Read the official problem statement on LeetCode
Solve on paper / whiteboard first
Implement the general problem-solving approach
Verify edge cases from the checklist
State time and space complexity aloud
Compare with the AlgoForge reference solution
Schedule a revision session

Revision notes

Multiply Strings (#43) — Medium. Pattern: general problem-solving. Complexity: O(m * n) time / O(m + n) space. Re-derive the invariant before coding.

FAQs

What is the time complexity of Multiply Strings?+

The reference solutions aim for O(m * n) time and O(m + n) space. Always re-derive complexity from the code you write in the interview.

What pattern does Multiply Strings use?+

It primarily maps to general problem-solving, within the broader topic of string.

Is Multiply Strings good for interviews?+

Yes — as a Medium problem it is a solid practice target. Pair it with related problems in the same pattern family for spaced repetition.

Where can I read the official statement?+

Open the official LeetCode page for constraints and examples: https://leetcode.com/problems/multiply-strings/

#	Title	Difficulty	Topics
5	Longest Palindromic Substring	Medium	string
151	Reverse Words in a String	Medium	string
161	One Edit Distance	Medium	string
186	Reverse Words in a String II	Medium	string
271	Encode and Decode Strings	Medium	string
306	Addictive Number	Medium	string
468	Validate IP Address	Medium	string
481	Magical String	Medium	string