Just instead of dp of string like he had used , use a dp which contains the parent node and the extra character (‘0’/‘1’) that was appended on it from the parent.

"

string multiple_Optimized(int A)

{

if(A==1)

return “1”;

// First represent the current charater that it obtain from its parent

// Second is the parent (initialized with -1 to check all nodes are visited once)

vector <pair<char,int>> dp(A,{‘1’,-1});

dp[1].second=1;

```
queue <int> Q;
Q.push(1);
while(!Q.empty())
{
int r = Q.front();
Q.pop();
if(r==0){
string str;
while(r!= 1)
{
str+=dp[r].first;
r=dp[r].second;
}
str+='1';
reverse(str.begin(),str.end());
return str;
}
for(int digit : {0,1})
{
int new_r = (r*10 + digit )% A;
if(dp[new_r].second == -1)
{
dp[new_r].second = r;
dp[new_r].first = char('0' + digit);
Q.push(new_r);
}
}
}
return "";
}
```

"