_2486. Append Characters to String to Make Subsequence.md

2486. Append Characters to String to Make Subsequence

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 03, 2024

Last updated : July 03, 2024

---

Related Topics : Two Pointers, String, Greedy

Acceptance Rate : 73.229 %

---

I'm realizing in hindsight that a dictionary wasn't necessary since I could just
Iterate through using two pointers and it would still be O(m + n)

This is what I get for doing it the moment I wake up at 630am lol

---

Solutions

• m2486 Daily v1.py
• m2486 Daily v2 two pointer.py
• m2486 v2.c
• m2486 v2.java

Python

m2486 Daily v1.py

# bottom 5% for both memory and runtime damn

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        if s == t:
            return 0

        # Getting the indicies of each value and storing them for O(1) lookups
        sSpots = {}
        for i in range(len(s)) :
            temp = sSpots.get(s[i], [])
            temp.append(i)
            sSpots[s[i]] = temp
        

        currentSpotT: int = 0
        currentSpotS = -1
    
        # Go until we can't find a index to use that's farther than our current spot
        while currentSpotT < len(t) :
            temp = sSpots.get(t[currentSpotT], [])

            if len(temp) == 0 :
                break

            while True :
                indCheck = temp.pop(0)
                if indCheck > currentSpotS :
                    currentSpotS = indCheck
                    sSpots[t[currentSpotT]] = temp
                    break

                if len(temp) == 0 :
                    return len(t) - currentSpotT
            currentSpotT += 1

        return len(t) - currentSpotT

m2486 Daily v2 two pointer.py

# V2
# Consistently 95% memory since uses O(2) memory space lol
# 30% region for runtime

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        pointerS, pointerT = 0, 0

        while pointerS < len(s) and pointerT < len(t) :
            if s[pointerS] == t[pointerT] :
                pointerT += 1
            pointerS += 1
        
        return len(t) - pointerT

C

m2486 v2.c

int appendCharacters(char* s, char* t) {
    int tPoint = 0;
    int sPoint = 0;

    while (s[sPoint]) {
        if (t[tPoint] == s[sPoint]) {
            tPoint++;
        }
        sPoint++;
    }

    int counter = 0;
    while (t[tPoint]) {
        counter++;
        tPoint++;
    }

    return counter;

}

Java

m2486 v2.java

// Around the [40, 50]% range runtime wise

class Solution {
    public int appendCharacters(String s, String t) {
        int pointerT = 0;

        for (Character c : s.toCharArray()) {
            if (c == t.charAt(pointerT)) {
                pointerT++;
            }
            if (pointerT == t.length()) {
                break;
            }
        }

        return t.length() - pointerT;
    }
}