leetcode question link?

[plush slate]

^ wanna practice

[prime hawk]

Not leetcode

[prime hawk]

How do I even know if it will pass all test cases now?🤧

[plush slate]

closest q?

[hoary sierra]

this is 2 pointer + greedy

#include <iostream>
using namespace std;

int main() {
    string str = "000010010101";
    int k = 2;
    int n = str.size();
    int l = 0;
    int r = n-1;
    while(l<r && k) {
        if(str[l] == '0' && str[r] == '1') { // Perform swap greedily
            swap(str[l], str[r]);
            ++l;
            --r;
            --k;
        }
        else {
            if(str[l] == '1') ++l;
            if(str[r] == '0') --r;
        }
    }
    cout<<str<<endl;
}

[prime hawk]

Did it worked for you 15/15?

Okay, but I guess TLE was for very very long input so not sure but lemme know if you know anything else

[prime hawk]

No idea, it was OA I don't think theres anything on leetcode

Similar to this or either I dontknow

[hoary sierra]

i didnt submit, im just guessing the problem based on the title you provided. but its fairly straight forward

p sure my implemenation is correct

[hoary sierra]

what was your approach?

[prime hawk]

First tried with something priority queue and till max k swaps, and then something greedy both supposed to be o(n*k)

[hoary sierra]

this is solved in O(n)

[prime hawk]

Then tried asking gp t but no luck so confused either I'm missing something or who knows

[prime hawk]

I mean o(n*k) is also o(n) k is swap number only👀

[prime hawk]

Btw did u do the Amazon OA?

[hoary sierra]

yea

im joining amzn soon

is this amazon OA Question?

[prime hawk]

Ohhh nice

[prime hawk]

Yea

Looks decent hard to me but might be easy for others

[hoary sierra]

k is a nontrivial constant that can be up to n, O(n*k) would be O(n^2)

[prime hawk]

Hmnn, btw u got same question?

[hoary sierra]

no, but ive solved similar

[prime hawk]

Or how you know the constraints? Coz I don't remember anything forgot to take pics

[prime hawk]

Hmnn

Pls tell them to give me finale

[hoary sierra]

does swap mean only adjacent or any 2 characters

[prime hawk]

Only adjacent 0 and 1

[hoary sierra]

oh. then its simple counting and greedy

not 2 poitner

def largest_binary_string_after_swaps(s: str, k: int) -> str:
    s = list(s)  # Convert string to list for easy manipulation
    zeros_before = 0  # Count of zeros encountered before the current index
    n = len(s)
    
    for i in range(n):
        if s[i] == '0':
            zeros_before += 1
        else:  # s[i] == '1'
            # Determine how many positions we can move the '1' to the left
            positions_to_move = min(k, zeros_before)
            if positions_to_move > 0:
                # Swap the '1' with the zeros before it
                s[i - positions_to_move], s[i] = s[i], s[i - positions_to_move]
                k -= positions_to_move
                zeros_before -= positions_to_move  # Update zeros_before after moving '1'
    
    return ''.join(s)

gpt code

[prime hawk]

But not sure first 6/15 then 10/15 tried multiple solution but hoping for best

[hoary sierra]

dont lose out hope ik someone who got 0/15 and 5/15 and got an offer

[prime hawk]

I guess tried this as well ig it was also 6 or 10

But not sure don't have anything saved

[prime hawk]

Yea will see how it goes

Hopefully my work style simulation went better

[plush slate]

why is amazon giving out borderline hards lol?

[prime hawk]

I don't know if this is hard or am just avg

[plush slate]

some people are getting mad questions

[prime hawk]

How soon they gave updates after OA?

[plush slate]

idk I dont have that process rn