This, you will have to try. Try run it full brightness for a while and if your phone charger get hot or the voltage drop is steep, you may need another power supply.
Cheap phone chargers capable of 1A is quite common out there now. Look those up.
The answer is "it depends".
If you want a flashlight, with a nice beam, then you need optics, thus it is much easier to use one high-power LED so only have to purchase one optic (lens or reflector).
If you want diffused light, then having many light sources (many LEDs) is easier to work with.
Now, if you use batteries, you'll be interested in the efficiency of your LEDs (ie, lumens/W) to maximize battery life. So you need to be aware of that. There is a compromise though, as LEDs with pleasant warm light and good color rendition tend to be less efficient. Very high lumens/W LEDs are usually "cool white" and low-CRI which isn't that good for stuff like reading or ambient light.
As well, are LED strips generally brighter than the individual LEDs, which are 15,000mCD each?
mcd (tmillicandela) has nothing to do with light output. A candela is a lumen per steradian, the latter being a unit of ANGLE. This means the same LED chip, which puts out the same amount of light (lumens) can be 100 mcd or 10000 mcd depending on how the optic in front concentrates the light into a wide or tight beam. If you want to make a lamp for diffuse ambient light, you need low-mcd, high lumen LEDs.
Each individual LED is, say, 3.3v and draws 20mA. for 20, that's 1.3Whrs.
W is power, not Whr which is energy.
Now, DO NOT wires your LEDs in parallel. Since all LEDs have a bit different voltage drops, the one with the lowest voltage drop will hog all the current, then burn. Then the next one will hog the current... etc.
If you got many LEDs, you need to put them in strings with resistors to equalize the current. Or use only 1-3 high power LED.
Losing less power on the resistor means putting more LEDs in series (ie, using higher voltage) but if you start from one 3.6V LiIon cell, boosting above 12V will also be less efficient. So 12V is OK.
12V LED strips will lose some power on the resistor. 3 high power LEDs in series will not (but may be more cumbersome to use, your choice).
Best Answer
The linked LEDs are designed for 12V not 5V. You would be better off with 5V smart leds. You can under drive the 5V ws2811 LEDs to about 3.7 volts.
Yes 3xAAA would be enough to power 3 of the 5V LEDs at a decent brightness. Preferably you want Alkaline not Heavy duty (aka zinc) batteries for a longer life. Alkaline AAA would have about 2000 mAh, so assuming full white 60 mA for 3 LEDs that's 180 mA so roughly 10 hours per battery set. That value is optimistic, but if you have different colors and brightness and off periods the run time will increase.
You could go smaller with lithium cells but make sure you get a protection circuit and a charging circuit. There are tiny lithium packs that are the size of match books. Those are typically 3.6v so you may need a step up voltage converter so that adds complexity and lowers the battery life. You would basically be making a usb power bank.
So your best bet is to go with a small usb power bank. I've had one that was the size of car key fob.